SRM475
うさぎ回=hos回でした。
300
うまいやり方がありそうな気もしたが、今回は確実に正のスコアを取ることを目標にしていたので、素朴に書く事に。最大ケースがサンプルに入っているし、シミュレーションしても問題ない大きさだった。シミュレーションなしの解法もあることをあとで教えられた。
204.19
600
フィボナッチだ。大きいし行列だ。整数除算があるけれど問題ないだろう。と思って書き始めたものの剰余をとるところで計算が合わない。やはり誤差が出てしまうので配慮が必要だった模様。除算回数は高々50回なので2^50倍で剰余をとれば大丈夫なはず、BigIntegerを使おう、というところで残り5分。書き換えが間に合わず。
想定解法2らしいが、1はどんな解法だろう。
Opened.
他にもバグがあったからすぐに通ったとは言えないけどね
900
戦略的にこんなものなかった。
Challenge
唯一600を出した人が、BigIntegerでうさぎの数を厳密に計算してから最後に剰余をとろうとしていたので、1000000番目のフィボナッチがまともな桁数のわけがないし、加減算がO(桁数)だろうが!と撃墜しようとしたものの、コピペで頭にスペースが入って受理されず。直している間に先をこされた。
シミュレーションを落とす気になれなかったので、一応読んだもののそのまま終了。
結果
204.19で92位。Div1で初の2桁順位。
600を出せていればもっと高いところに行けたはずなので、もっと頑張っていこう。
感想
問題の一捻りに上位陣の格の違いを見せつけれられた気がします。