3完。昨日よりコンディションは悪かった（体のことで）。最初のうちはやや集中が弱かったが、だんだんいつも通りの感じに。そんなに影響なかった気がする。昨日も今日もコンテスト中に何も食べてなくて、それでけっこう集中できている。まあ食べるのってけっこう大変だからね。いつ食べるか、どうやって袋を開けてどう食べるか、こぼしたら掃除、お腹の心配、そういうのを全部排除できるわけで、食べない選択は普通にあり。元気がなかったからそう思うだけかも。
BとCはそこそこ簡単そうに見えるのに、しっかり時間かかってるんだよな。
A - Yet Another AB Problem
BBBAAAみたいのに変化させることはできない（元から一致してれば0回）。昨日のABCのBじゃん。Tを左から見てSと一致しない初めてのBは、それより左のAとペアで操作する必要がある（そういうAがなければ-1）。ここまではいいが、じゃあBじゃなくてAはってなるとわからない。一致しないBとできるだけペアにしたいが、複数あればできるだけ左のものを選ぶのがよさそう（左から見てるので上位互換になる）。本当にそれ以外の方法がないかはわかってなかったけど、まあ実装に入る。スタックみたいに考えて、AのストックがなければBは左の適当なAとペアにして、ストックがあればそのうちの一つとペアにする。効率悪くてもいいから相手がいるかは常にチェックしておく（最も左のAと最も右のBの位置を前計算する）。最後に余ったAを1個ずつ処理する。
途中で行き詰まってBを考えていたのはいい動きだった。解説も括弧列なのは意外だった。こういうのって確信を持って提出するの不可能なんだよなあ。今でも証明わかってないし。
B - Arithmetic Progression Subsequence
10以下って最初に読んでも、最後まで問題文を読んだらその内容に圧倒されて忘れてるやつ（たまたま問題文を目に入れたのですぐ気づいた）。良い組以外を数える？指定された数を避けるだけでも問題になりそうなのに、長さ3って。そういう部分列は色々なところに存在しそうで難しい。長さ3なので真ん中固定は思いつくが、据わりが悪いので左固定に。最悪100通り考えても間に合うし、等差数列と左端を固定すれば、最短でどこが右端になるか求められる（10種類の数それぞれについて次に現れるのがどこかを前計算しておく）。ここから、後ろからやるのがいいかと思ってそうでもなくて混乱してた。結局普通に前から。(l, r)のlを固定して、rについてある位置から右なら良い組になるが、それがどこからかを知りたい。そこから左にある等差数列の右端が最も左にあるものの位置が知りたい。SWAGでできると思い実装に入ったが、後ろからの累積minでよかった（書いてしまったのでそのままSWAGで実装した）。
解説が鳩の巣原理でびっくり。実装の重さがどのくらいかはやってみないとわからないな。面白い問題だった。
C - Prefix Mex Sequence
具体例を辛抱強く追っていくと、S_iが1のときは1通り（嘘）、0のときはM通りかM+1通りになるとわかる。そして、サンプルはM通りで通ってしまう。なんかDPが見えそうだけど、何を状態とするか。mexがMより大きくなるかどうかが重要（mexを避けて1通り減るかどうかが変わる）なので、0以上M以下の整数のうち何個埋まったかを状態にしてDPできそうだ。実装上は、Mに1を足してM未満の非負整数を扱うことにする。Mが大きいこともあるが、DPの範囲はmin(M, N+10)とした。
サンプルが弱いのは十分わかっていたが、2ペナを喫した。いつもサンプルに助けられているぶんで、制限時間もきつい中なので、仕方ない（実力的に）。2WAの原因は、M以下の個数が増えない遷移を分けてなかったことと、M以下が全部揃ってるときS_iが1だと詰むのに気づいてなかったこと。後者がけっこう致命的。NよりMのがはるかに大きいケースがあるんだけど、なんかそのイメージで大きい数も置けるように思ってしまったが実際はMまでで、Mより大きい数は出てこない問題なんだよな。そもそもMが大きかったらこの問題は簡単なんだよ。
D - Triangle Card Game
かなりシンプルに見えるが、Aliceは同じカードを2回選べない。その辺りの場合分けみたいのが相当嫌らしそうで、ARCのこの位置の問題という感じだ。あまりやりたくはない。三角形の条件を考える。まず1つ目の整数は固定する。2つ目と3つ目がどうだったら条件を満たすというのを平面に描いてみる（なんか45度の長い長方形）。うーん場合分け（なのか知らんけど）までも辿り着けない。
（追記）解説の方針でAC。難しくてやりたくなさすぎて時間がかかった。3手のうち、1手目を全探索。2手目は、斜め長方形（この内部をAliceが3手目に選べばAliceの勝ち）を下から見て横に切った太さが初めて最大になるところで切って場合分け。その下側は、Bobにとって一番下の選択肢が上位互換なのでまずそれをチェックする。Bobの勝ちならAliceはそれを選ばない。Bobの負け（下側にカードが存在しなかった場合も含む）なら上側もチェック。斜め長方形は右上へ無限に伸びているが（それは長方形じゃないだろ）、左下へも無限に伸びているとしてよい。なぜなら、下側でBobが負けるときのみ見ているので余計なものが追加されるとしてもそれはAliceが勝つBobの手のみで、これから上側でチェックする「Aliceが負けるものが一つでもあるか」に影響を及ぼさないため。さて、ここで「あるBのカードに対する1手目を除いたAのカードまでの距離の最小値」の最大値を知りたい。その最大値が1手目のA_iより小さければ、Bobは何を選んでも負けるのでAliceはその1手目を選べば勝ちとなる。そういう1手目が一つもなければBobの勝ちとなる。最大値を求めるには、セグメント木を使う。各最小値を求めるのには、Aをソートしておいて二分探索を使う。このとき、左右で最小値を与えたAのインデックスにBのインデックスを記録しておく（記録されるインデックスの個数は高々N*2個なのでこれにlogが付いても間に合う）。1手目のカードを除くには、記録された全てのBのカードに対して、右側の最小値であればもう1個右のAを対象に最小値を更新する（普通に左側との最小値をとる）（はみ出さないように注意）。書き忘れていたが、Bobが一番小さい数のカードを出すときは、二分探索でAliceが勝てるカードの区間を求め、その区間長から区間に1手目のカードが含まれるなら1を引いたものが0なら、その1手目はBobの勝ちとなる。
