4完。時間をオーバーしたものの自力で全問通せたのは嬉しい。やっぱこのころ（というか現行のレーティング制度が始まってからの2年間くらい）の問題面白いよな。
A - Signboard
コピペした"CODEFESTIVAL2016"と1文字ずつ比較。
B - Qualification simulator
これは珍しくリアルタイムで参加したほうが有利な問題だ。海外の学生も予選を通過できる。問題文の通りにやるだけだが、条件が見た目より多い分量でかなり大変だった。
C - Gr-idian MST
家と家の間の道路ってさあ、家と家を結ぶ線分に垂直なものを想像しちゃうじゃん。まあ問題文やサンプルをよく読むと気づく。問題名の通り最小全域木の問題だ。小さい例を作りクラスカル法で図を描いてみる。盾に並んだ横線は全部同じコストだからまとめてやってしまっていい。縦と横に分けて、反対側でやった回数ぶん（連結になっていたら線を引かないので）線を引く回数が減るっぽいことに気づく。証明はできないが色々試してそれっぽいので実装に入る。実装は軽いけど、書く前は全貌が想像できなかった。そういう実装は勉強になってる気がして好き。
D - Greedy customers
ストーリーがつかみにくい。要するに、棒がN本並んでて水平に弾を発射して当たったらその場所より下が消滅して落ちる、弾の位置は整数のみで棒を消滅させてはいけない、みたいな状況。できるだけ多く弾を当てたいので、低い場所に当てたい。手前から順に当てていくことを考えると、それよりいい方法は存在しないように思える。証明はわからないけど。そうだと仮定して実装する。最初の棒は1ずつ削って高さ1にできる。次の棒が高さ2以下だと何もできない。3以上のときは2ずつ削っていけるし、最後の1発（次どこを撃っても高さ2以下になるとき）で上から1の位置を撃てば高さ1にできる（低いほうがのちの選択肢が増えて得）。境界をきっちりするのが大変だが、自分より左の棒の現在の最大の高さ+2を残して何回撃てるか割り算で求めて次の1回で高さ1にすればいい。
なんとなくで問題をACしていくの、AtCoderを始めて半年とかの自分がそうだったと思う。証明を心がけたり、未証明でやっていることを自覚したりが、そのころと比べればできるようになった。この点では本当にAtCoderをやっていてよかったと思う。
（解説を見て）『そしてこの連結操作は、「これ以降 x 座標 i と i + 1 を同一視する」という操作です』なるほどなあ。何か超頂点を持って連結を管理とかはちょっと思ったけど、そういう捉え方。ちょっと抽象的になると自分が持ってない概念になって、そうなると「図を見てなんとなく」を言語化できない。
E - Lexicographical disorder
1100点だけど1時間以上残ってるので解けないまでも自分のやれるところまでやる時間としては十分。どの文字が大きいかが毎回変わるのはきつい。しかし、トライ木を思いついた。全部の枝を見て現在の文字より小さいものの個数を足していけば何番目かわかる。経路上に他の文字列がある場合がややこしいが、枝に進んだあとそこで終わる文字列があれば1を足すようにすればいい。提出してTLE。
まだ30分以上あるのでデバッグの時間としては十分。同じ文字列に対して大量のクエリが来ることもありえるので、当然のTLEだった。そこで、クエリを先読みして同じ文字列に対するクエリをまとめて処理する。書き始めて気づくが、トライ木を辿るときにそのまとめた個数ぶんの時間を毎回かけることはできない。ただ、文字の順番は26!通りもある。まとめて処理はできないように思える。文字と文字の比較は26^2通りしかないのでそこでどうにかならないか。あるいは、注目する文字を固定しその文字の枝の寄与だけを計算するとか。上手く行きそうに思ってやっぱ全然ダメを繰り返す。時間がないので変数名がごっちゃごちゃになった（これは反省点）。最後に、寄与を26^2通りに分けて計算しておくことを思いつく。26^2が掛かるのがQに対してで済んでいるので、計算量もそんなに重くならない。経路上の文字列の個数は共通。文字の順番を表す各pに対して、c0がc1より小さいならこれを足すという値が求まる。
しかしサンプルの実行で落ちる。落ちるはずがないのに落ちていて最後の数分間頑張ったが原因がわからなかった。そもそも落ちないはずのTLEコードを貼っても落ちたので、原因はトライ木の処理ではなかった。まとめて処理するときに、ソートして同じ区間を求めるやつってやっぱり複雑で、最初に-1番目の文字列に対して処理をしていた。落ちないはずなら別の場所を見る発想がほしかったね。
（解説を見て）ちょっと待って。26^2の大小関係の情報があればそれを使ってソートして元の順列が求まるがそれは26!通りあるってどういうこと。（しばらく考えて）2^(26^2)通りじゃん。それはダブってる情報もあるから26!より大きい。いや間抜けに見えるかもしれないけどこういうかつて考えたことがあるような分野でもこの勘違いがパッと正せない。難しい（けど決して届かないわけじゃない）問題でめちゃくちゃ時間がかかるのはそういうところなんだよな。高々26^2個のブール値で順列の情報を表せるということがわかってなかった（26*log(26)個くらいあればいい）。
