ぷよぷよクロニクル 第２回おいうリーグ S級リーグ まはーら vs しょたぺろ 50先 実況枠 - YouTube
これ見てたんだけど、ちょうど決着したくらいのタイミングで、開いておいたyukicoderタブから通知が来たのでそのまま開始。相変わらず感情は死んでいるが、最近暖かいし今日は色々楽しみがあって少しはほぐれてきたかなあ（まあ、クソな現状で感情だけでもという状態だけど）。
No.656 ゴルフ
forと打ったのをBackSpaceしてrforにした。微妙なところ。size()を得るのがめんどくさいのと、cとs[i]の違い。
No.657 テトラナッチ数列 Easy
事前に求めておけばいい。求めるのが難しいイメージあったけど、それは第N項をO(1)のメモリで求める場合だった。今回はO(N)のメモリで全部求めるので、書くだけ。
No.658 テトラナッチ数列 Hard
まさかの上位互換。絶対こっちを先にやったほうが得だったじゃん（あるいはそうでもないのかなw）。ただ、コンテスト体験としてはこういうのもいい感じ。
とりあえず最初の100項を表示させてみた。特に規則性は見えない。次に17^4を計算する。テキストエディタ（Mery）上でjsを実行できるようにしてあるので、Math.pow(17,4)と打ち込む。これ面倒だよね。代替案を考えないと。Googleか（検索窓へ17^4と入力した瞬間に答えが表示されてる）。結果は83521。これをそのまま使おうとしたが、境界が怖いので90000にした。
さて、連続する4項は高々17^4通りしかない。それ以外の情報は保存されないので、必ず17^4以下の周期でループする。よって17^4回程度の計算量でこの問題は解かれた。いや、具体的に解かないといけない。初期状態が0,0,0,1だが、そこへ戻ってくる保証はない。あ、解説を見ると確かに異なる状態から合流することはないので保証あるっぽいですね（まだあんまり実感できないけど）。
まあコンテスト中にそんなことを思い付いて証明する時間はないので、保証がなくてもOKな解法で行くわけだ。第90000項の時点では既にループに入っている。だってその90000個（くらい）の連続する4項の中に同じものが存在するから（鳩の巣原理）。んで、その辺りの4項を固定して、同じのが現れるまでループを回す。
最初の90000項は計算済みなのでそれを使う。それより後のクエリだったら、90000からの増分を周期でmod取って90000に足せばいい。
No.659 徘徊迷路
迷路に解があるかDFSやBFSで求めるより真に難しい問題だなーとか考えていく（この問題が解ければ何が解けるか、で問題の内容を探っていく）。Tが10^8でシミュレーションできないくらい大きい、許される誤差が10^-6でそこまで甘くない、ちょっと無理そうに思えた。
次の問題も見つつ、いずれも難しそうなので将棋のニコ生に戻った（将棋も解説も最高でしたね）。その後も頭の中でたまに考えたりしていて、途中までシミュレーションするとして誤差は指数関数的に減るんじゃないかと気づいた。証明はできなかった。解説には100000回くらいで行けるとあるが、自分もそう思っていた。まあ実際にコードを書けば行けそうな感触は得られるのかな。盤面が狭いし、そこまで病的なパターンもないだろう。なんか長い迂回路があると収束遅くならないかなーとか心配してたけど。まあいずれにせよ大して考えてないので。
