歯の詰め物が欠けた、スマホが再起動ループ、ARC中トイレが微妙に間に合わなかった、ARCがズタボロだった。悪いことが重なると気持ちが普段と違うステージに行く。上手い言葉が見つからない。「絶望」とか「茫然自失」とか、一面ではそうだけどけっこう違う。
3完5ペナ。証明難度が高くて苦手、と思っていたけど、自分の状態があまりにも悪く、調子がいいときなら苦手と思わなかった可能性すらあると思った（わからない）。
A - Ternary Decomposition
最小でも1なので、KがNより大きかったらできない（気づいてなかったが、制約でそういうケースは除外されていた）。3の冪は全部奇数なので、NとKの偶奇は一致する必要がある。さて、3の冪であることが本質である場合と、そうじゃなくて他の近い数でも解法が変わらない場合がある。後者をかなり警戒した。ナップサックみたいに大きいほうからDPできるのではないか、いや状態数も3冪みたいになりそうで意味ないか。Kは大きいけど、大きいならほとんどが1になる（できる）はずで、解法は存在しそう。一方でKが小さすぎて厳しい場合は、例えばK=1ならNが3の冪か判定する能力を（正解コードは）持つはずだし、K=2だともうちょっと複雑になる。難しすぎる。これが300点！？貪欲を試しに書いてみるが、サンプル通らない。ひえー。
BCも読んでわからないので、ここで順位表を見る。難しすぎて順位表が大惨事になっていると思っていたら、実際はみんないいペースでABを通していて驚いた。
自分のコードを見直すと、普通に変数名をミスっていた。貪欲に（残りを全部1で埋めてオーバーしない範囲で）置ける最大のものを置いていくという方針でサンプルは通る。途中経過を出力させると、構成も正しくできているようだ。これで提出してWA。貪欲で構成できないはずの 17 3 を試してみると、N=K=-1になってOKみたいな判断してる。0になったら終わるようにしてAC。ACしただけ。貪欲の正当性はもちろん何もわかってないし、その貪欲をこれで正しく実装できているという確信もない。
3進法は全く考えもしなかったねえ。
（追記）パリティさえ合っていれば、バラしてK個にできる。
B - Switching Travel
問題文は飛ばさず読んだと思うが、かなり怖い見た目なのもあり、サンプル1の図に全て持っていかれた。頂点1からだと思って考えていた。サンプル2の説明はちゃんと読んでなかったと思う。
十分条件でしかないけど、違う色の頂点へだけ移動できるとしたときのDFS木において、両端が同じ色の辺を結んで長さが奇数の閉路ができればYes。これを提出して15WA。直接の祖先と結んだ閉路じゃないと途中で行き止まりになると気づいた。DFSと閉路、本当に難しいのだった。これを提出して16WA。増えるのは意味がわからない。頑張って考えるがめちゃくちゃしんどい。同じ色の祖先に戻った時点で勝ちなんだよなあと言いながら。だいぶ経って誤読に気づいた。誤読は前から疑っていて、問題文を読み直したりしていたが、ざっと（文字ではなく）意味をとっていく感じで、まあ疲れてるとどうしてもそうなってしまうが、それだと「好きな頂点を 1 つ選んで」は「頂点1」に見えてしまう。で、好きな頂点からスタートできるなら、もう最初の提出みたいに01010みたいな閉路があればいいから、各頂点からDFSして提出、21WA。増えるの！？見直すと、0をiに書き換えるべきところがもう1個あった。提出して21WA。変わらない！？よく考えると違う連結成分の同じ色につないだらダメだ。訪問済みフラグを世代管理する。これでAC。
（追記）UnionFindで、違う色へだけ動いて行き来できる同値類に分けて、その中で同じ色を結ぶ辺があるか見る。
C - Reversible Card Game
トイレで残り1枚のケースと残り2枚のケースを考えていた。思ったよりAliceの思い通りにならない。だいぶ経ってから、0と何かが書いてあるカードだと思っていいという当たり前のことに気づく。これは酷い。そうなると、0が表か裏かが一致するカード同士は比較ができる。上位互換がわかる。貪欲に選んでいいんじゃないか？たくさん通されてるからテキトーな貪欲でいいんだろうみたいな思考嫌いだが、じゃあどうすればいいかというと。
Aliceは0でないものがあれば最大のものを裏返す。そうでなければ表が0で裏が最小のものを裏返す。Bobは0でないものがあれば最大のものを取り除く。そうでなければ表が0で裏が最小のものを取り除く。2人で同じような操作になって意外だった。multisetを2個使う。上位互換の盤面になることを使って証明できないか少し考えるが、脳が限界。頑張って実装する。AC。悲しき敗戦処理AC。
（追記）言われてみればパリティだなあ。奇数の場合は協力しても全部は取りたい向きで取れない。実装が、最終的にはシンプルになるものの、取りたい向きのカウントと差の最小求めるのでけっこう整理するのが大変。
D - 1D Coulomb
読んだだけ。まだ5分あったけど、考える気にならなかった。「Cまでもう少し早く通せていればDをコンテスト中に時間をかけて考えることができたのに」とも思わなかった。
（追記）考えていったら括弧列になってびっくりした。先に現れた符号を開き括弧としていくつかの括弧列に分割できる。括弧列の中では対応する括弧同士が対消滅する。DPで解けそうだと思い、対応する括弧の距離を考えていたが、これは難しい。まず、最も距離の和が小さくなる配置は、()()()()のようなものだ。そこから開き括弧を左へ一つ動かすたびに距離の和が2増えると観察から予想できる。また、括弧列をまたいでも、どうせ括弧列の電荷はゼロなので、現在の位置とこれまでの＋の個数から同じように計算できそう。具体的にどうやってDPするかというと、括弧列の先頭と同じ符号ならそのまま遷移して、そうでないなら個数の累積和のぶんだけ距離を加算する。距離の和を求めるため、通り数も必要。求まったら2倍してベースの距離であるNの通り数倍を足す。解説を見ると、コスト（距離の和）を全部＋に乗せることもできるんだね。また、メモリ使用量は増えるが、累積和ではなく単に＋と－の個数でDPするのはきれいな考え方だ。
