FII Code 2020 Round #3

　Bまでの二完でした。A, Bの後Dを考えていて、実装終わらずに終了。とはいえ、仕方ない面もある。

コンテストへのリンク
コンテスト後のツイート

（このブログの記事は、主に、当時の自分のツイートを参考にして書いています。なら、そのツイートも載せておいた方が良いのでは？　と思ったので、今後はできるだけ載せます）

Confused Robot

　これを飛ばしてDにいった。

　Sをひとまとめに見て、「それぞれの地点から、S一回分進むとどこへいくか？」を考えてダブリングするのが自然。

　が、これだとPython/PyPyで間に合うのか分からず（制限時間が長めなのも不安材料）飛ばした……んじゃないかと思う。あまり記憶にないけど。

　二個ほど他の人の提出を見たけど、大体そういう方針で解いているようだった。

　公式解説には、ダブリングを使わず、「S一回進んでも動かなくなる回数」を前計算すれば良いと書いてある気がする。けど、これって最大N*M回かかるのでは？　よく分かりません……。

　O(N*M*S)でいけるなら実装してみようと思ったけど、よく分からないので実装してません。

　ダブリング解でもPyPyでちゃんと書けばACできそう……？

追記）ダブリングなしで「S一回進んでも動かなくなる回数」は求められることに気付きました。グリッドの各マスについて、「S一回でどのマスにいくか」を調べておけば、

・S一回後に自分自身に戻るマスは0回（以後Sを実行しても動かなくなる）
・S一回後に0へ行くマスが1回

　という風にして、DFS/BFSで求められますね。

　ただ、それを求めても、「S一回進んでも動かなくなるギリギリの回数」は最大N*M回あると思うので、O(N*M*S)では無理な気が……。（やっぱりダブリングが必要では？）

Double Palindromes

　コンテスト中ずっと考えていて、コンテスト後実装が終了したので提出したらTLEでした。

　Manarcherの解説はすぬけさんの記事が分かりやすい。

　その上で、アルメリアさんが解説している方法が使えます（この解説の例題の中に、この問題があります）。いや、この記事は勉強になりますね……。こういう観点で問題を見たことがありませんでした。

　これを読むと、コンテスト中に考えていたセグ木を使う方法は本質的には間違っていなかったようですが、BITを使うことで高速化できそうです。

　というわけで、もしかするとアルメリアさんの方法を使えばTLEにならないのでは？　と思い実装してみたのですが、いつの間にか、CS AcademyではPyPy/Python3が使えなくなってました！（え？）

　「Non zero exit code = 127」というエラーが返ってきてどうしようもありません。

　Python3だとTLEなのは仕方ないですし……。まあ、しょうがないですね。

　勉強になったので良かったと思っておきます。