ここ1日くらい気分が沈んで（何かあったわけではなくなんとなく）のんびり過ごしていた。そういうときにありがちな、コンテスト中に心拍数がやたら上がって、解法の厳密性の確認にやたら時間をかけてしまう感じのやつになった（時間かかるのは普段からという気もするが）。でもEFをそれなりに早く解けて、久々に"天才"を見せてしまったかなと（これだよ欲しかったのは）。
A - Registration
TがSより1文字だけ長い制約であることを確認して、t.pop_back()。問題文を読むのにけっこう時間を取られてしまった。
B - Easy Linear Programming
B問題だしどうせ 1<=A,B,C<=100 とかだろと思って、長さA+B+Cのvectorを構築する解法を考えていたところ、なんと10^9。これは、A以下か、そうでないならA+B以下かで場合分けする。最近のB問題は甘えさせてくれないな。
C - Skill Up
最近のC問題むずくないすか。まあよく見ると実装が少し重いだけ。問題文を読むのにかなり時間かかったけど、どれを買うか全部試せばいい。
D - Teleporter
最近やったPAST2のEを思い出してしまうが、Aは順列と限らないことに注意。まずダブリングが浮かぶが、順列でないにしても高々N回でループすることには変わりないので、ループするまでシミュレーションする。そこまでにK回以上テレポートしていればシミュレーションの記録から答えがわかるし、Kがもっとでかいならループに入るまでの回数を引いてからループの長さで割ったあまりを計算し、それでループ内の何個目が答えかわかる。必ずしも町1に戻ってこないことに注意。ミスが怖くてガンガン変数を宣言していったが、もう少し空間計算量の定数倍を減らせるだろうなあと思いながら書いていた。
E - Colorful Blocks
O(N^2)のDPができそうだなあというのを最初に思う。それを考えたのちに高速化するという方針がある。まあF問題も一応目を通してから本格的に考える。まず、DPをするにしても、具体的に何色かというのは関係ない。隣同士が同じ色というのが何箇所あったかだけが重要だ。図を描いて考える。1個目と2個目が同じ色かで分岐（同じ色が1通り、違う色がM-1通り）、2個目と3個目が同じ色かで分岐。ここまで描いて、パスカルの三角形に見えた。まさに合流（同じ色の組がそれまでに何個あったかが同じとき合流）の仕方が同じだ。最終的に組の個数は0からN-1までのN通り。0からKまでコンビネーションを計算して、違う色がたくさんあるぶん(M-1)^(N-1-i)を掛ける。サンプルが合わなくて「えっ」と声が出たが、最初の1個は1通りではなくM通りだった。Kまでの和を求めて最後にMを掛ければよい。
F - Bracket Sequencing
括弧もPAST2のKでやったので経験が生きた。まず、括弧を開くのを+1、閉じるのを-1として、和が0でなければダメ。それに加えて、途中までの和が負にならなければOK。ということで、N個の文字列は、+1,-1に変換したときの和（これをdとする）と、途中までの和の最小値（これをmとする）だけに注目すればいいのではと気づく。そのように変換し、じゃあどのようにつなげればいいか。具体的に構成する解法かどうかもわからない中でしばらく考える。まずdが正でmも非負のやつは使ってしまっていい。mが負のやつはそうやって稼いだ貯金がないと使えないので。dが正でmが負のものは、やはり貯金を稼ぐために早く使いたい。ここはmの絶対値が小さいものから。dが正なので、後になるほど状況は改善する。dが0以下のものしか残ってないとなったら、もう状況は改善しないので、mの絶対値が大きいものから使う？それは違いそうだ。状況を激しく改悪するものを先に使ってはいけない。考えてみると、あるS_iを使った（使えた）ときd-mのぶんだけ余裕が残るわけで、最終的に可能であるならd-mがより小さいものを後から使えば問題なさそう。考え直すと自信がなくなってくるが、さすがに時間も時間だし実装に入る（ここまでも、考えを寝かせる時間として実装はできるところまで進めており、いい立ち回りだった）。難しいのはソート（ソートしたら実際に構成して確かめるだけ）。まずdが正かどうかで判定、それが同じならdが正かどうかで場合分けしてmかd-mで判定する。なんとかAC。よかったー。
