今日解いた競プロの問題。

EDPC-J Sushi: 解説AC。寿司1個の皿の個数、寿司2個の皿の個数、寿司3個の皿の個数という3つを管理するDPをすればいいというところには自力でたどり着けたが、いくら数式をこねても答えが上手く合わなかった。敗因は数学的な詰めが甘かったからというのもあるが、主な敗因は「DPテーブルの値は遷移元の値の和になるはず」という思い込みを元に配るDPでやっていたからだった。解説を読んだら計算式は線形和じゃないし、実装は当然集めるDPというかメモ化再帰だった。

DPの値は遷移元の値全てを単純にモノイド和なりなんなりするのでは求められない場合があり、その場合は選択の余地なく集めるDPにせざるを得ないということを身に染みて覚えた。言われたら当たり前なんだけどな…

EDPC-K Stones: grundy数の考え方でいく。grundy数は苦手だがこいつはかなり単純なのでどうにかなった。

1. それ以上取り去れない状態なら必敗局面
2. 必敗局面に遷移させられるなら必勝局面⇔必勝局面にしか遷移させられないなら必敗局面

1から基本的にほとんど必敗局面であり、2をもとに必勝局面を決めていけば良い。

EDPC-L Deque: 区間DPするだけ。区間DPは短い区間から順に調べていくが、この問題設定のゲームは最大の区間の状態から始まってターンが巡っていくので、Nの偶奇および今調べている長さの偶奇によって場合分けする必要があるのだけ面倒。メモ化再帰ならもう少しその辺の詰めが楽なのか。

---

3回目のワクチンを打った。明日の体調はどうだか。

今日の筋トレをする前にワクチンを打ってしまったので今日は筋トレができなくなってしまった。失敗。

---

今日はEDPC-Jを延々試行錯誤していたら時間が経ってしまった。失敗。