■ [SRM]SRM529 
http://community.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14722&rm=311123
- 250
- やるだけゲー
- サンプル通ったので提出したあと、手で1から50までテストケース作って動かしてみたら何カ所もミスってた…
- 泣きながら再提出
- 確かに、あまり賢くないミスりやすい実装ではあった
- サイズ小さいから効率悪くても全探索で良いよねーというの、何回か出てきてるけどなかなか浮かびづらい
- 600
- 擬似コード（？）を解析していくと、bag1を2から1つずつ増やしつつ、bag0(=N)を割り算してみて割り切れるまで続ける、というようなことをやっていることになる
- 数えていくと、Nの1以外の最小の約数をPとして 1 + Σ[2<=i
- N=13とかで書き出してみると、ceil(N/i)が2や3になるiはたくさんあるのでこいつらをまとめてやると良さそう
- 一方、ceil(N/i)が大きな値になるとceil(N/i)として出現する数がまばらになってくるので、iについて一つずつ調べる
- より具体的には、
- ceil(N/i)<10^6までの場合は、ceil(N/i)==Mとなるiの数は ceil(N/(M-1))-ceil(N/M) みたいな式によって各Mに対してO(1)で求められる
- N/i>=10^6の場合は、i<=N/10^6<=10^12/10^6==10^6 だから、iについてループ回して全部調べれば良い
- というわけで O(√N) で計算できる
- しかしNの最小の約数を探すところで、10^6未満の素数でしか調べていなかった関係で、10^12以下の最大の素数を与えると無限ループになってしまっていた…
- そのほか、MODとるのを1箇所忘れていたり、平方分割するのを10^6じゃなく10^5にしてしまっていたりと細かいミスが
- この2つはこの問題で落ちる原因になってたかどうかは微妙なとこだけど
- Challenge
- 600と900が即落とされているのを尻目に250に集中
- 落ちそうなのがない
- 結局システムテストでも全員落ちてなかった
- System Test
- 250は通った
- 600は落ちた
- 161.79 + 0.00 + 0.00 + (50*0-25*0) = 161.79
- 497位/811人
- 2037->1953
やっぱり再提出可能なコンテストかどうかで戦い方全然違いますね。1発勝負難しい
最大の素数でテストしてないのはかなり致命的なミス。時間あったのに
