2013年10月04日

ウォーミングアップにフィボナッチ数を高速に求めてねというのをやってみたら，思いのほか難しかった様で？　開始直後に見て回ったコードはC言語の文法では無いものが多数あったり．まあ，後半では動くプログラムを書いている人が多かったのでみなC言語を思い出してくれたと思いたい．どこぞのエディタには main 関数内に fib とかいう関数が定義されてたけど……　まあ gcc 使えと言っているので正しいといえば正しい．

そして出題のミスを発見．n が大きくなると int に入りきらないので，てきとうな正整数 Q で割った余り（つまり fib(n) mod Q）を求めれば良いとしたのだけど，これをやると最大でも Q^2 - 1 の周期になってしまうので，Q が固定なら周期を先に求めておいてハードコーディングすると定数コストで答えが求まる．しかも，周期が最大の Q^2 - 1 になるようなことはあまりなく（とりあえず Q=3 は最大周期になるが，これ以降数万くらいまでの Q では全然ダメで，Q は超えるけど Q の定数倍くらい），出題に使った 3万程度大きさの Q は 3千程度の周期しか無かった．前もって周期の長さをチェックしておくべきだった……