1完。3時間あって未証明ACを1個しただけ。AGCを楽しむことができない自分の頭の程度にがっかりする。特に立ち回りが悪かったとは思わない。
A - Right Side Character
色々考えたけど全くわからん。軽く実験するとだんだん揃ってくる。いくつか試して末尾は最初の1回にしか変化しないように見えたので提出してみたがWA。色々考えたけど、結局やることが実験しかない。長さ8の文字列を全列挙してWAになったケースを探す。いや最初からこれ書けって話なんだけど、実装力が終わってるのでそうそうできない。実際、めちゃくちゃバグらせて時間を食った。特定のパターンだと末尾が最後に変化するまでに時間がかかる。依然としてそれっぽい解法も降ってこない。答えがBになることが少ないと思い、全部出力させてみると、今度はパターンが見えた。末尾がBでかつBAを含まない、でよさそう。ACした。ここに至ってもなぜそれでいいのかわからないし、この1時間は、結果の出ない観察と実験コードのデバッグにほとんどの時間を使っている。ゴミ。
B - Split and Insert
解けるわけない見た目をしている。
逆から考えると、部分列を後ろに持っていく操作になる。昇順に揃えるのが目標になるのでやりやすい。後ろに持っていくサイズに応じてコストがかかる。Cはreverseしておけばいい。「連続する昇順」の部分列を後ろに持っていく操作のみでいいと仮定するとDPができそう。頑張って書くが、サンプルが合わない。大きい値を出力しているので、もっと良い方法があるということだ。自分のコードが間違っている可能性もあるので、A問題でやらかしてたのもありかなり時間をかけて確認した。実際バグもあったが、出力は変わらなかった。終了後に思いついたのは、5 4 2 3 1。23をまとめて取り出さず、42と53で取り出してから45というのができる。これだとコストは改善しないけど、なんか方法はありそう。
C - Mex of Subset Sum
Aをやっている間にBCは読んであり、Aを通したあとはCをメインに考えていた。
Nが60なのは出力すべき値が2^60くらいで済むようにするためだろう（今気づいたけど10^17にもならんやん）。bitDPを思い浮かべると、左右対称の1次元ハンコをA_i間隔で押す感じ（tourist回の中央値求めるやつ思い出してた）。100万まではこれでできるので、大きいところをどうにかできないか。しかし相当色々な形がありそう。作れないのだけ持つのはけっこうきつそうだが。K=1としてもよくわからない。1時間くらい考えてBへ。
Cは面白そうだったのになあ。マジで何もできなかった。何も見えなかった。目が悪すぎる。
