2完。青コーダーにとっても面白いAGCだった。あとは俺が面白い人間でありさえすればよかった。いやまあ時間があっという間に過ぎたのでコンテスト体験としてはだいぶよかったと思う。
A - atcoder < S
可能かどうかは意外と簡単で、aだけなら不可能でそれ以外は可能。で、サンプルのatcodeer => atcodere みたいのが大変だと思ってしまった。tacodeerでいいんだよね。最初に出てくるaでないものを持ってくればよさそう。aazは1回の交換でいいので、まあ文字数も少ないし交換しながら毎回比較する。問題はよりよい手段がないかだが、少なくとも先頭2文字がaaではダメなのでそこへa以外を持ってくることは必要。最速で持ってきてるのでOK。
いやあ時間かかった。もうずーっとサンプルに思考を誘導されてた。何文字目で初めてatcoderより大きい文字が出るか全探索という方針を考えていて、とりあえず実装してたらadtnみたいので2文字目をターゲットにして2文字目と3文字目を入れ替えてもtでは上回らないけど3文字目はcより大きくなっていきなり成立みたいなのを見つけて、まあ証明できないと思ってたら本当に穴があるパターン。いやAGCでこんな複雑になるわけないと思ってB問題も少し考えたりして何か出てこないかと粘っていたら、2文字目がaでないとき1回以下じゃんと。
B - Bracket Score
Nマスあって括弧を置いていくイメージで考えて、対応する括弧との間には偶数個のマスがある。分割しても最初のkマスの最大とかを見ても結局N^2になってしまい、どう考えていいかわからない。Nマスの中でどれを'[', ']'にするかだが、2マスずつの塊にすれば自由に選べる。そこから更に改善できるか。思ったより自由に配置できるのではないかとカマかけてみる。で、直前の'['の位置を使ってDPで行けるのではと思いつく。'['が開いてないか、奇数個前に'['があるか、偶数個前に'['があるか。遷移で混乱して時間はかかったが、やたら簡単に解けた。しかしサンプルが合わない。
"[([])]"があるのを見落としていた。開き括弧であれば間に奇数マスしかなくてもいいのだ。サンプル2が親切すぎる。対応する開き括弧と閉じ括弧の位置は偶奇が異なる必要があると気づく。つまり位置が偶数と奇数で個数が同じ。なんか十分条件でもありそうだ(間違ってたDPでの経験値が生きている)。ならば、偶奇で分けて降順ソート、上から取っていって最大値を更新していけばいい。構成できる証明だが、偶奇隣り合ってるものからペアにしていけば、その中は(一番内側なら)偶数個だから違う括弧で埋めれるし、奇数個の隙間も"()"で埋めて1個にして対応する括弧内はそれが偶数個残るので2個ずつペアにすれば。正直、証明は全くできていないのだが、証明できそう(俺が証明できそうとは言っていない)なのでこれ以上コンテスト中に無限時間消費してもねということで実装提出した。
C - Penguin Skating
碁石を動かして考えた。動きはそれなりに限られそうだが、混乱する。少しして、左から順に右へ動かし、右から順に左へ動かせばよさそうと気づく。O(N)の実装が書きなれない処理で大変だがなんとか短時間で書き上げる。しかしサンプルが合わない。これもサンプル3が親切だなあと思ったが、何が反例になるのか最後までわからなかった。これはN=3000でもわからん。
(2022/10/22追記)インデックスを引くのを思いついて解けたかと思ったら全然届いてなくてでびっくりした。要するに、ペンギンに幅がないものとして考えればいい。計算量を考えると、かなり複雑な処理が必要になりそう。しんどいので解説を見た。いや端に0とL+1を追加して端だけ動かないなーとか思ってたけど、まさかこんな。ペンギンとペンギンの間にある「泡」のほうが本質だったとは。AGC052のBを思い出した。端の情報量やペンギンが両側に関係してくる様子が少ししっくりきた。まだよくわかってない。