あのいかつい配点から、まさかの3完早解き回。最近のAtCoderは崖を作るのが上手すぎる。
最近ずっとそうだったように調子はあまりよくなかった（ABCや典型90の復習でもあまり頭が回らなかった）が、昼寝は少しだけだけどできたし、ぷよぷよ観戦をかなり早めに切り上げのんびりトイレに行ったりして直前の時間を過ごした。ラムネも用意してコンテスト中にたくさん食べた。昨日の反省を生かし、クーラーを付けっぱなしにした（コンテスト中は体が熱くなり体感温度も上がる）。スピードは出なかったが、順当な思考を重ねることはできて、それがはまる得意セットだった。
A - Remove Substrings
両端の文字が異なるときは1回。そうでないときを考える。両端の文字が同じなのでそれと異なる文字を探す。1個では無理。もちろん0個でも不可能。2個あって隣接しているときは2回で可能（1回では無理）。他はどうも不可能っぽい。最後の1回は両端が異なる文字になるので、ラス前の操作をして消した隣に元の文字列の両端と違う文字がないといけない（これも、最終的に元の両端の文字が残っている証明も要るから厳密じゃないんだけど、まあそれができるなら全部消せてるはずなんで）。正しそう。すっきりとした証明が見えないのだけど、順位表を見てもみんなペナを出さずに瞬殺しているので、まあ正しそう。ということで提出。
B - Greedy Division
とりあえずBCを交互に考えるが、問題文の読みやすさと解いている人の多さからBに集中した。
状況は単純だが何をしたらいいかわからない。例えば「最初のK個を使ったときの通り数」とかでまとめることができない。順番がバラバラで数えられる見た目をしていない。W_i が小さいので、何個か選んで合計をいくつにするのが何通りというのは求まる（その合計が 2^N になる）。とりあえずこのDPを書く（やや手間取る（やっぱこの典型DP慣れたとはいえ苦手で頭の働きが悪いと苦しい））。で、半々に分ける具体的な方法を一つ提示されたとき、それを達成する順列がどんなものかを考えた。高橋君が取るものと青木君が取るものを上下に並べ、横幅が合計の半分という図を描く。最初のころ「最後に大きいの来たらピッタリにならないなー」とか考えてたけど、これよく見ると半々に分かれてさえいればこの図に対して順列が一意に定まる。どんな並びでも達成できるし、1通りしかない（合計が少ない順に番号を振っていくだけ（合計が等しいときは高橋君が取る））。ここで足りない情報は、半分を何個で達成したかだ。これも含めてDPする。100^4なのでまあなんとか間に合う。実装が重くなっていたこともあり、DPテーブルは3次元から2次元に変更。ここでもけっこう手間取る。個数を降順に更新すれば上書きしていける。結果的には、3重forの中で1回足し算してるだけの単純なコードに。検算のため合計が 2^N になるか確かめるコードを書いたりした。あとは階乗を前計算しておいて計算。K個で半分になるそれぞれについてそれを高橋君が取ることにすると K!*(N-K)! 通りちょうどの等しくなる順列が生成できる。K=N-K の場合や、半分を選んだら選ばれなかったものも半分になることによるダブりを心配してやや混乱したが、まあ素直に足していけばよかったと気づきサンプルも合った。
C - Roughly Sorted
（Bと比べて）問題文の読解が難しいCのほうが、頑張れば解けそうな安心感がある。
最小の操作回数ということは、直前は条件を満たしていなかったということ。転倒数（と呼ぶことにする）がK未満のものしかなかったら直前の状態がないので操作回数0の1通りのみ（後で気づいたがこの場合分けは要らなかったっぽい）。本題は転倒数がちょうどKのiがいくつかある場合。最後の操作はK+1をKにするもの。操作を逆にやっていくことを考えて、どんな操作が許されるか。関係ないやつは動かせない。一つだけならどんどん後ろへ持っていく操作になりそう（いつでもやめられる）。転倒数って、その数の左だけ見ればわかるけど、自分より小さいものが右にあればそっちへの寄与もあるわけで、混乱した。ちょうどKのものが複数あるとき、追い越すことはできる。どう考えていたか覚えてないけど、みんな「ちょうどK」だから、左にあるものほど小さい。図で見ると単純な場合の数に見えて、でもどうやるかすぐにはわからないという状態だったが、落ち着いて考えると右から順に決めていけば何回上へ移動するか掛け算していくだけだ。追い越せることに気づいたのが大きい。Nが小さく、楽な実装で済んで助かった。
DEF
不可能そうな見た目のBCに対し、Dはわりと簡単そうに見える。EFは何言ってるかわからない感じだが、まあ問題文の表面的な意味はわかる。AGCでコンテスト中に全部の問題読む展開珍しいな（読めること自体はいいことだ）。やや「座っているだけ」になってしまった。Eはまさかの門松列か！？Dについては、'o'はわりと自由に動けて、'x'が高さ1を要求する、括弧だけなら転倒数みたいに行ける？どうも'x'の扱いが難しいということそう。この見た目でtouristさえ通していないというのがヤバすぎる。
