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前後まで計算してストップしたほうが、今回のようなややこしいバグを含まなくて良かったかもしれません。

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

prosho007prosho0072012/01/30 17:54Mi_Sawaさん

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

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

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

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

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