| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
91分6完（3ペナルティ）で47位でした。しばらく集中できていない自覚があったけど、何とか。
Fが難しかった。先週と今週は、5完難易度と6完難易度の差が大きいセットですね。こういう傾向になっていくのかな？ABCコンテストでも難問の経験が積めるのはありがたいです。
問題C
過去問 の経験から、左右からの累積を持てばよいというのが一瞬で見えたので、その方針で解きました。一般に、配列から1元抜いた状態をたくさん考えたいときに使えそうなアイデアですね。
この問題は、単に除くものが最大値じゃなければ最大値。そうじゃなければ2番目の数を答えるだけだったようで、若干、パターン学習の弊害がｗ
問題D – Preparing Boxes
下から決めようとして誤答したりしました。約数と倍数を勘違いしてる。
問題E – Sequence Decomposing
最長の単調減少列をとってくればよい。それらを起点に塗り始めて漏れが出たとしたら、減少列を延長できて矛盾します。
あとは典型題。減少なこととか、等しい値を許すことなどに注意して。大小順は入れ替えてから増大列として実装しました。
問題F – Permutation Oddness
不動点の個数ごとの数え上げ（撹乱順列）とかが頭をよぎるが、同様の方針をとってもdpできない。例えば「$1$と$4$がswapされます」みたいに2点を入れ替えたとして、残った問題が小さい場合に帰着できない。問題を拡張してもうまくいかない。
全探索類似も考えた。1, 2, 3, …, n の移し方を持たずとも、移り先として占める部分集合を持てば計算できそう。と思ったが、階乗オーダーが指数オーダーになる程度では足りない（$n$ が小さいので一応考えちゃうよね）。
やっぱり何とか「左から見ていくdp」ということで頑張って考える。例えば、1番をその場に残すか右に運ぶかだけ決めて、1番の到達位置は確定させない。1番を右に移動させた場合は、$\{1,2\}$ が2マス目に居て、そこからその場に留めるか、右に流すか、左に流すかなどを決める（1番は戻さない）。
この方針で、（その場所で左右に移す数の個数、これまでに移した回数の合計）を持ってdp更新できる形になった。方針が立っても、実装がなかなか大変でここに30分かかった。右移動だけではなく左移動分の数え上げも考えないといけないし、移動してきたものを左に押し戻さないようにするなどに注意しながら、きちんと重複・漏れを回避した式を立てないといけない。
慎重に慎重を重ねて実装し、バグなく1発AC。残り時間が10分を切っていました。細かい気を遣うところの多い問題だったので、これでWAが出ていたら10分じゃ直しきれたか怪しい。ぎりぎりでした。
