Bのみ1完。Cは読んだだけ。
A - Underclued
まず全部の問題を開いて、Dまでを5秒ずつ見て、Aをやる。
N*2個の和の情報で分類できて同じグループ内で全部同じ数になってる位置の個数だよね（Aの選び方に依らないことを確認したい）。少し考えて分からないので実験コードを書く。N=4やN=5で2^(N^2)通りの行列を全列挙しmapで分類する。個数としてありえるものを出力させて、難しそうなのでBへ。順位表は早い段階で見ていた。その個数を実現する配置の例を見ることも思いついていたがやらなかった。
B - Typical Permutation Descriptor
条件を読むのがめちゃくちゃ大変。頑張って読む。0からNまでの長さN+1の順列が何通りあるか。左端は0で固定。1からNまでの各iについて、自分より左の位置を選び、順列の選んだ場所は自分の位置より小さく、間は大きい。小大大大大[自分]という感じ。「条件を満たす順列が存在する」ということで、小と自分の間に（自分より左の）他人の大があると矛盾するっぽい。色々な例を手でいじって観察するのをひたすら繰り返す。グラフで表せないか。トポロジカルソートの数え上げかと思いググると、ABC041の解説で一般には難しいと書いてあり参考になった。グラフが木になった場合に解けるかを考えると、最初は（1番目は部分木の根として）2番目をどの子に入れるかなどを考えて迷走したが、部分木のサイズから根の分を除いたものからいくつか選んで子の部分木に割り当てることを繰り返せばいいので、二項係数で簡単だった。大きさ順に並べると、順番に並んだり割り込みが発生したりして、グラフが木になりそうどころか（図を描くと一番手前側しか残らなくて）割り込む対象が常に1列になっている。ここでstackを思いつく（天才）。これにより不定形のもやもやを（正しいかはおいといて）型にはめることができ、具体的な実装が可能になった。スタックから除いたやつだけ辺を張って、最後にスタックに残ったやつにも辺を張って、0を根としたサイズN+1の木ができる。
サンプルが合わず、0から複数の辺が出ていておかしいと思い調べると、スタックの使い方が雑すぎた。popしたものは辺をつなぐが、最後は（stackのtop()ではなく）現在の位置につなぐ。きれいには書けなかったけど、処理自体はまあ簡単。未証明どころの話じゃなくてそれっぽくまとめただけだけど、内容的にきれいなのでビルドするたびにサンプルが通りそうだとは思っていた。最終的にサンプルが通ってそのままACした。解けそうになった時点では時間に余裕があったけど結果的に13分しか残らない。
解ける気がしない問題を観察し続けてACまで行くのは本当に久しぶりの体験で、よかった。
