Hatena::Grouptopcoder

prosho奮闘記 RSSフィード

2012-01-30

続 FHC R1 Aのバグ検証

20:43 | はてなブックマーク - 続 FHC R1 Aのバグ検証 - prosho奮闘記

追記:原因がわかったので編集しなおしました。

追記の追記:Sigmarさんのご指摘で真の原因が判明しました。前の記事のコメントを参照してください。

前の記事の通り、R1は落ちてしまいました。今回はAのバグを探りたいと思います。

まず、正解者のコードを実行して得た結果answer.outと、自分がsubmitしたファイルA.outのdiffをとります。

$ > diff A.out answer.out
1c1
< Case #1: 567503
---
> Case #1: 4256235

となります。

Case1のS = 8512466のときだけ値が合わないようです。

そこで、前の記事にあるコードの最後の出力部分を少し書き換えてみます。

while(test++ < r){
		cin >> S;
		int res = INF;
		int resi, resj;
		for(int i = 1;i*i <= S; i++){
			if(S % i == 0){
				int j = S / i;
				if(res >= memo[i] + memo[j]){
					res =min(res,  memo[i] + memo[j]);
					resi = i; resj = j;
				}
			}
		}
		printf("Case #%d: %d (resi = %d, resj = %d) (memo[resi] = %d, memo[resj] = %d), answer = %d\n", test, res, resi, resj, memo[resi], memo[resj],memo[resi] + memo[resj]);
}

これで実行した結果、

Case #1: 567503 (resi = 1, resj = 8512466) (memo[resi] = 1, memo[resj] = 567502), answer = 567503

となります。memo[8512466] = 567502という計算が間違っています!

たぶん、二項計算の途中でオーバーフローがおきてるのでしょうか??

まだよくわかってませんが、nCrでn=23, 4前後まで計算してストップしたほうが、今回のようなややこしいバグを含まなくて良かったかもしれません。

Facebook Hacer Cup 2011 R1

11:57 | はてなブックマーク - Facebook Hacer Cup 2011 R1 - prosho奮闘記

Qual はo-oで通過。Bはちょっと考えて大変そうだったので早めに諦めました。

今日の3:00にR1が終了したので、軽く振り返ってみようと思います。

コードや考え方が間違ってる可能性もあるのでご注意を。

(なお、問題説明は省略します。これ読んでる人の多くはR1に参加してると思うので)

最後に、誰か、はてなの日記でコードを綺麗にハイライトしてくれる方法をご存知でしたら、是非教えてください~(追記:←解決しました)

追記:結果は残念ながらxooでした。。Aのどこが悪かったんだろう・・・、challenge phase対策の格好の勉強材料になりそうですw

未だにバグがわからないので、気付いたら教えてくださると嬉しいです。

Checkpoint

ポイントは組み合わせ nCr を計算して、nCrに対する最小のnを記憶しておくこと。nCrの計算にパスカルの三角形を利用しました。

// include部分は省略
typedef long long ll;

int memo[10000002];

// pascal's triangle
void prepare(){
	queue <int> as;
	as.push(1);
	memset(memo, -1, sizeof(memo));
	for(int turn = 1; turn < 10000001; turn++){
		ll sz = as.size();
		ll pre = 1;
		while(sz--){
			int a = as.front(); as.pop();
			if(a > 10000000) continue;
			if(memo[a] == -1) memo[a] = turn;
			if(a + pre <= 10000000) as.push(a + pre);
			pre = a;
		}
		if(turn % 2 == 1 && pre != 1 && 2 * pre <= 10000000) as.push(pre * 2);
	}
}

int main(){
	prepare();
	int r, S, test = 0;
	cin >> r;
	while(test++ < r){
		cin >> S;
		int res = INF;
		for(int i = 1;i*i <= S; i++){
			if(S % i == 0){
				int j = S / i;
				res = min(res, memo[i] + memo[j]);
			}
		}
		printf("Case #%d: %d\n", test, res);
	}
	return 0;
}

Recover the Sequence

1,2,...,Nを求める答えとしてマージソートして逆変換する方針で解きました。リストの使い方が楽なのでpythonで書きました。

import sys

done = 0
S = ""

def solve(lst):
    n = len(lst)
    if n <= 1:
        return lst
    mid = n / 2
    first_half = solve(lst[0:mid])
    second_half = solve(lst[mid:])
    return merge(first_half, second_half)

def merge(lst1, lst2):
    global S, done
    result = []
    while len(lst1) and len(lst2):
        if S[done] == '1':
            result.append(lst1[0])
            lst1.pop(0)
        else:
            result.append(lst2[0])
            lst2.pop(0)
        done += 1
    result += lst1 + lst2
    return result

def checksum(lst):
    res = 1
    for i in lst:
        res = (31 * res + i)
        res %= 1000003
    return res

def main():
    T = int(sys.stdin.readline())
    test = 0
    while(test < T):
        test += 1
        N = int(sys.stdin.readline())
        global S, done
        S = sys.stdin.readline().strip()
        done = 0
        lst = [i for i in xrange(1, N + 1)]
        ret = solve(lst)
        memo = {}
        for i in xrange(len(ret)):
            memo[ret[i]] = i
        ret = [memo[i] + 1 for i in memo]
#        print ret
        print "Case #%d: %d" % (test, checksum(ret))
main()

Squished Status

まず、MODが4207849484とデカイのと、compressed sequence中の0の扱いに注意する必要があります。

以上に注意すれば、比較的に簡単な問題かと思いました。

自分はメモ化再帰で解きました。


static const double EPS = 1e-5;
typedef long long ll;
const ll MOD = 4207849484;
string S, M;
int keta_max, M_int;


int myatoi(string n){
	int res = 0;
	rep(i, n.size()){
		res *= 10;
		res += n[i] - '0';
	}
	return res;
}

ll memo[1001];

ll rec(int index){
	if(memo[index] != -1) return memo[index];
	ll res = 0;
	if(index == S.size()){
		res = 1;
	}
	else{
		FOR(i, 1, min(keta_max + 1, (int)(S.size()-index) + 1)){
			string tmp = S.substr(index, i);
			if(tmp[0] == '0' || myatoi(tmp) > M_int) continue;
			if(index + i <= S.size()){
				res += rec(index + i);
				res %= MOD;
			}
		}
	}
	return memo[index] = res;
}

int main(){
	int n, test = 0;
	cin >> n;
	while(test++ < n){
		cin >> M >> S;
		keta_max = M.size();
		if(S.size() > 1000){printf("Case #%d: %lld\n", test, 0); continue;}
		M_int = myatoi(M);
		ll res = 0;
		memset(memo, -1, sizeof(memo));
		res = rec(0);
		res %= MOD;
		printf("Case #%d: %lld\n", test, res);
	}
	return 0;
}

追記:A落ちてます・・・。二項計算の所が怪しいのかな・・・

Mi_SawaMi_Sawa 2012/01/30 16:44 >|cpp|
そーすこーど
||<
ですかね.
http://hatenadiary.g.hatena.ne.jp/keyword/ソースコードを色付けして記述する(シンタックス・ハイライト)
に書いてあります.

prosho007prosho007 2012/01/30 17:54 Mi_Sawaさん

情報ありがとうございます!お陰様でハイライトできました。
Mi_Sawaさんは無事にR1通過したようですね。R2も是非頑張ってください!

SigmarSigmar 2012/01/31 01:21 Aのパスカルの三角形の計算ですが、恐らくprepare全体の中で一度でも要素が10000000を超えた場合(a+pre>10000000もしくは2*pre>10000000となった場合)、その後2*preをasに一切追加しないようにする必要があるのではないかと思います。

prosho007prosho007 2012/01/31 16:17 Sigmarさん
ご指摘ありがとうございます!ああ、なるほど!!
確かに2*preの追加に注意すべきでした。パスカルの三角形じゃなくなりますね!
自力では全く気付きませんでしたたが、お陰様で目の前の霧が晴れました!!本当にありがとうございます!!!

RajuRaju 2012/11/16 15:51 Normally I'm against killing but this arctile slaughtered my ignorance.

pylrlrcweqpylrlrcweq 2012/11/16 22:17 ndjBap <a href="http://gssmxjyfajrd.com/">gssmxjyfajrd</a>

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/prosho007/20120130