2完。いい立ち回りができたのが嬉しくてたくさんツイートしちゃった。Aが解けないときに「レーティングはどうでもいい」という思考になれたのがよかった。好みではなさそうなセットに対し、それでもAGCを最大限楽しむ動きができた。
A - ABC Identity
「互いに異なる」という条件が(そういう条件があるに違いないと何回も読み直したのに)目に入らなかった。なので、それなら簡単じゃん(N%3回だけ1文字ずつのを取り、残りを同じ文字だけで3回)と実装をするが、途中で見つけて考え直す。まあ、つかみどころのない問題なのでこの実装はそれほど損にならない。
手で実験をしていると、分布は偏っても均等でも簡単で、多い文字を取るように3回取れば均等に残せるような気がした(残った文字を3等分して各区間で均等なら3回でできる)。全体を3等分してみる。最初の区間でAが一番多かったとして、BAC, CAB, BCA, CBAの4通りに上手く分配すれば最初の区間以外のAを全部取れる、と思う。上手く行きそうな気配しかないが、どうすればいいか全く見えてこない。さて、そもそもこれで行けるなら別の楽な方法が存在しそうだ。1回部分列をとるときに、同じ文字は同じ(さっきの3等分した)区間からしか取らなくて行けると仮定すれば、取り方はちょうど順列の6通りになる。連立方程式になるとつらそう。もう少し観察すると、1つの値を仮定すれば残りも全部簡単に求まる。O(N)で全探索ができる!未証明だが1時間経っているので実装に入る。実装もけっこう苦戦した。その中でも「同じことを2回書かない」を実行できていたのはえらかった。3*3*3の配列の中の6個だけ使う。一つでも負の数があったらアウト。そうでなければ、その個数だけ区間から取っていき、その様子を出力。未証明AC。
結果的に1時間以上かかった問題に対し、落ち着いて「座ってるだけ」や「考えすぎて疲れる・混乱する」にならないように立ち回れたのがよかった。Aが不可能になったらBを少し考えて「Bのほうが不可能だ」になってAのやる気を復活させたり。「3つの区間に分けてしまってもどうせ大丈夫なんでしょ?」のように、苦手なタイプのAGCによくあるパターンを決め打ちするという普段あまり好まない戦い方を選ぶ判断もよかった。
(解説を見て)難しすぎる。
B - ABC Supremacy
そういう場所はrotateできる。全く解ける気がしないのでとにかく手で実験して雰囲気をつかむ。最初に考えていた方針は、rotateできる(01201のように順になっている)区間で文字列を表現するみたいなの。区間の境界は3ずつずらすことができるので、それをなんか正規化して揃えてから文字を比較みたいなのを夢見ていた。でも、回転させて隣と合わせて合併みたいのが扱える気がしなくなって断念。他に、3文字の塊を文字として扱うとか、文字swap2回で言い換えてとか、いくつか考えてたけど無理そう。rotateできる場所が1箇所しかないときに、動かせる場所を左に移動させるのは手でやっていた。自由度はそこまで高くなさそう。移動のとき、まあ文字が増えたり減ったりはしないから当然とはいえ元の文字の並びがそのままスライドしていた。操作は可逆なので、例えば操作で実現できる辞書順最小がわかればそれを比較するだけだ。それで実装していく。rotateできるものはどんどん左へ移動させる。実装して気づいたが別に辞書順最小じゃなくても正規化できればよい。3つ組のバブルを全部左に寄せて012の形にする。残りの文字はそのままの順番で残っているはず。提出してWA。
じっくり考え直す。01[201]2のように[]内を回転させたケースを忘れていた。これは、同じ処理を何回も繰り返せばよさそうだが、計算量がダメ。eraseが高速にできるvectorがあればいいが、どうするか。まずmapを考える。インデックスに文字を持たせる。計算量が若干気になるが多分2秒には収まるだろう。なんでやめたんだっけ。昨日のABCで使った双方向リストも考えた。こちらを採用した。慣れないので手探りの実装。結果的には、0からN-1までのインデックスと番兵的なNをつなげ輪にした。Nがスタート地点とゴールを兼ねている。現在の位置から3つとれないならループを抜ける。とれたら順になっているか確認してリンクを付け直す。新たな3つ組を見つけるために、一つ前からではなくもう一つ前から再開する(戻る回数はO(3つ組の個数)なので、全体でO(N)は維持している)。慣れない複雑な実装で、さすがに不安だったので変換後の文字列を表示させ目で確認してから提出した。ここでYESとかも含め何も表示されず悩んだが、0を'A'に直す必要があった。WAを出してから25分程度かかった。これも未証明AC。
(解説を見て)スタックかー!いやー呑まれてたな。
C - Weird LIS
読んで考えただけ。でもそれができるだけの15分が残っていたのはよかった。1しかずれなさそうだけど、どんな形なら順列が存在するか各数について求めるのかあ。