Medium筋トレ3日目: SRM566

SRM566 Medium "PenguinEmperor"
■時間
５時間ほど。

■試した解き方
daysPassedが小さければ、各町にいける経路数を配列に持って更新していけばいいだけなので簡単。
しかしdaysPassedが最大で10^18なので、これは現実的ではない。

numCities+1日目に動くのと1日目に動くの同じだということに着目する。
つまり、numCities日動いた場合の各町の経路数をキャッシュして、それを(int)(daysPassed/numCities)乗すれば、numCities*(int)(daysPassed/numCities)日目まではすぐに計算できる。
　→2乗を掛算していく方法使えばO(log(daysPassed/numCities))でできる。
残りは地道に更新していけばいい。

⇒以上までは分かったが、最大のケースでtimeoutしてしまうためeditorial見た。ちょこちょこ無駄を消して（実は最初の実装でマトリクスとか使ってた）、大丈夫になった。

1st submit:
OK

■Editorialの解き方
同じかんじ。

■反省
解き方は一発で分かったが、細かい実装でえらく時間食った。
これを11分で解く人とか魔人。