3完。ABは脳への負荷が大きく時間かかるし、Cはみんなが得意そうな数え上げ、Dは時間あれば解けそうだけど無理だった。ということで苦手セットかと思いきや、実は得意セットらしくhighest更新。
開始40分前くらいにトイレ行ったんだけど、直前になってまたしたくなり、仕方なく開始を待ってトイレに行ってトイレでABを考えていた。スマホでAtCoderにログインできるようにしといたほうがいいかなあ（できるようにした）（さすがに、20:57にスマホだけ持ってトイレ行くのは勇気要ると思うけど）。
コンテスト中に地震があって、遠かったけどそこまで大きい地震でもなかった。
A - XXYYX
捉えどころがない。先週のARCのAと違ってかなり嫌だと思った。まず、文字列を左から見ていったときにXがYに切り替わる回数がB、YがXに切り替わる回数がCであり、この差が1より大きいとNoになる。判定はそれだけでいいかもしれないし、そうじゃないかもしれない。ふわふわしていて困る。XXとYYが両方あったら、どこかでXとYが切り替わっている必要もある。改めて考えると、XYもYXもない場合、XXとYYが両方あったらダメ、片方ならよい（両方ないケースは制約より無い）。XとYが切り替わる場所があってBとCの差の絶対値が1以下なら、XYとYXを配置したのちにXを太らせてXXにする（Yも同様にする）ことで構成できる。ということで提出。
B - XYYYX
XをYにして損することはない。YをXにする必要が出てくるケースもあるというのが厄介。なんとなく、Kが大きいケースを逆から（N個全部反転してからN-K個選んで反転する）考えてみると、都合のいいことにKがXの個数以下のケースだけ考えればいいことがわかった（KがXの個数以上のケースを考えるか迷ったけどまあ普通にこっちで）。これはなかなかにARCだなあ。ここからもかなり面倒な展開が続く。最終的な方針は、まず初期状態のYYの個数を数えて、K=0ならそこで終わる。Kが0でないとき、Yが存在しないなら最初の操作ではYYが増えないので答えから1を引いておく。Yが存在すれば1回の操作でYYが1個以上増える（KはXの個数以下）。YとYの間を埋めたときだけYYが2個増えるので、ランレングスとって端以外のXの個数を小さい順に。これは貪欲でいい。長いXの区間をとってもメリットがない。若干怪しかったけどAC。
C - YY Square
DPするだけっぽくて簡単そう。軽く実装しようとしてみると、Yの個数を持って3乗のDPなら簡単だけどそれを高速化してねという話だった。実装は、少し前に解説放送で見た1次元vectorを2個持ってswapしながら使うやつを採用（最高速ではないけど、メモリ使用量が少ないから速いし実装も楽）。3個の値を持つ。そこまでの経路の数、その時点でのスコア、そこまでのYYの個数の期待値。1行目を計算して、2行目からはまず先頭を同様に計算して、一般の場所ではその2つを合わせたようなことをする。
Yが隣り合うという条件はわりと見かけ倒しだった。前と今がYのときにカウントする（そういう遷移をする）だけ。個数の2乗は、K個から1個増えたときにK*2+1だけ増える。つまり個数の期待値がわかっていれば、それを2倍して1足すことでいけそう（経路数はわかっているので掛けてスコアに足す）。ほんとに期待値でいいのかというのは、Kが10,1のときと7,4のときで同じだからみたいなイメージで、じゃあこれが3乗だったら同様の方法でできるのかとかも全然わからなかった。あとは、期待値を求めるときに割り算が出てくるのでmod 998244353で0にならないか心配したが、経路の数は二項係数だから2000より大きい素因数は含まれないと思った。割り算をなくせれば一番よかったが、その余裕はなかった。もっと楽な方針はありそう。swapの位置間違ってたのと2つ合流するときの期待値の計算をやってなかったのでサンプル通らなかったけど、そこを直してサンプル通ったのでさっさと提出。サンプル通ってから式の順番を入れ替えなきゃいけないことに気づいたりして見切り発車だったけどAC。B問題とC問題はけっこう怪しかった。
（追記）0乗和と1乗和と2乗和を持ってDPできるのかあ。自分のも大体同じだけど、1乗和を期待値で持っているのでコードが長くなっている。そのまま持つのも考えたけど、そっちだと和にまとめてしまっていいイメージができず回避してしまった。今度は端を場合分けせずにまとめて書いた。初期値が反映されてなかったり（dp[0]からdp[1]へ遷移する流れでdp[1][0]に初期値置くとは思わんやん）1乗和に0乗和ではなく1を足していたりしてかなり時間がかかった。
D - YY Garden
横の線をいくつ引くか固定すると、例えば2本引いて3つに分けたとして、縦の線はYを6個ずつに分ける必要がある。時間があれば解ける問題に見える。いくつに分けるかは、全体のYの個数の約数だけ考えればいい。Yの個数=a*bとして、横の線をa-1本引いてa個に分けることとする（縦の線も同様）。各行（各列）に何個のYがあるか前計算しておく。縦の線を引ける場所は区間になるのでその幅を求めて掛け算していく。次に横の線だが、縦の線に自由度があるときもYのないところを動くだけなので縦の線は可能なものをどれでも固定して考えて構わない。縦の線によって分けられた全ての場所でYがちょうど2個になる場所を全探索（メモリアクセスがここで高速になるように縦横の順番を考えてある）。ここでO(H*W)かかってしまうが、約数は少ないだろうし（Yの個数が最大2000個と勘違いしていたが2000^2個のこともあるやんけ）、O(W)のチェックで多くが弾かれるだろうし（ハックされそう）、そもそも実現可能なa,bは少なそう（ほんとか？しかも実現可能でなくても計算時間変わらない実装な気がする）なので、いけると思った。
どうだろうなあ、Yを対角線上に配置したら約数32個で余裕だったし、Yの密度が高いとO(W)のチェック通らなくなるし、TLEするケースが存在しない可能性も高そうに見えるが。ていうか2000*2000/2以下の最大の高度合成数は1441440で288個らしい。これはTLEしないね。288倍遅いケースはたぶん存在しないし、あったとして3秒なら余裕がありそう。
この実装はコンテスト中に終わる気がしなかったけど、終了3分前になんか書きあがったので提出してWA。そこからのデバッグにめちゃくちゃ時間がかかった（編集距離の大きなミスはなかった）。ツイートしたけど、縦線の柵を左右に動かせるのは真ん中だけというかそもそも端には動かせる線が存在しないのを考慮してなかった。全ての横位置に番号振ったとき1大きい番号が発生するの忘れてREになったしその対策でvectorを1大きくしても計算ずれたままだし。最後には、「bは0にならないはずだよな」とずっと思っていたのがYが0個なら普通に0になるというバグが残っていた。
（追記）解説読んで「なるほど～」って感じだった。Yの個数=a*b*2としたときに、aを1からHまで動かしてたけどbがW以下である必要もあるの気づいてなかった。2次元累積和だけでやる場合、横の線の自由度はb*2の倍数をカウントして0とa*b*2以外の積をとればいい。0だったらできない。2個ずつ入ってるかの確認も累積和でO(a*b)になる（これも見えにくい）。アルゴ式の高度合成数一覧便利すぎ。
