WUPC 2019 C - Choose Your Characters

• 問題
• AC

勝てない相手キャラがいないような最短の区間を尺取り法で求める。つまり、$\operatorname{dp}[i] :=$キャラ$i$が勝てるキャラの数、として各区間について正しい$\operatorname{dp}$を求めて、$\min_i \operatorname{dp}[i] >0$になるような最短の区間を探せばよい。

具体的には、最初に

$S(i) :=$ キャラ$i$が勝てないキャラの集合（同キャラ含む）

と言うデータを作っておく。区間を伸ばすときは$\operatorname{dp}$全体に1を足してから各$k \in S(i)$について$\operatorname{dp}[k] \mathrel{{-}{=}} 1$とし、区間を縮めるときには$\operatorname{dp}$全体から1を引いてから各$k \in S(i)$について$\operatorname{dp}[k] \mathrel{{+}{=}} 1$とする。$\operatorname{dp}$にセグメント木等を使えば簡単。

---

ようやく尺取り法の間違えにくい書き方にたどり着いたのでメモ。

• ok関数とng関数で相互再帰する。
• 常に半開区間$[l, r)$を扱う。(ok l r)は$[l, r)$が条件を満たすときに呼び出され、(ng l r)は$[l, r)$が条件を満たさないときに呼ばれる。rはこれから追加される位置であり、lはこれから除去される位置である。
• (ok l r value)のように区間に関する値を受け渡す場合、valueは常に区間$[l ,r)$に対応する値になるようにする。
• 最適値を求める場合はok関数の冒頭で更新する。