考察
非goal cellの値は、四方向へ進んだ後のdist+1のうち小さい方から二番目になる。Aokiが最良方向を一つ禁止しても、Takahashiは残る中の最良を選ぶからである。未知値を再帰式から直接解くとcycleするが、有限distの小さい順に確定すると、隣接する有限値が二個確定した瞬間にそのcellの二番目の値も確定する。盤外方向は動かず同じ状態へ戻るため、有限解を作る有効neighborとは数えない。boundaryで有限neighborが一つしかないcellは、その方向をAokiに禁止されるので到達不能になり得る。あるcellが確定したとき影響するのは四近傍だけであり、一つのcellはcount=2の一回だけqueueへ入るため、H×Wが900万でも線形処理で済む。
採用する候補: 全goalをdist0として始め、各cellで確定済みneighbor数を数えるretrograde BFS
queueはdist非減少で出るため二個目に確定したneighborのdistが二番目に小さい。countが2になったcellをそのdist+1で確定し、各grid edgeを定数回処理する。
棄却する候補: 各cellのsecond-min方程式を値が変わらなくなるまで反復緩和する
自己参照とcycleがあり収束回数を制約内に保証できず、有限状態がgoalから距離順に広がる単調性を使っていない。
distを∞、goalsを0でqueueへ入れる。distの小さい順にcell vをpopし、未確定の各grid neighbor uのfixedNeighborCountを増やす。2になった瞬間dist[u]=dist[v]+1としてpushする。最後に有限distを全て加え、∞cellは問題指定どおり0寄与とする。
典型の発動条件
ゲームの後退解析
発動条件: min/max双方の選択がある到達gameで、terminalから勝敗・手数を逆向きに確定できるとき。
goalを基底に、相手が一手を妨害しても残る二番目の遷移値から状態を確定する。
k-th smallest の多源BFS
発動条件: 状態値がneighbor値の第k小値+1で、値を小さい順に確定できるとき。
各cellはk個目のneighborがpopされた時点でdistを決める。
局所count伝播
発動条件: 確定済み後続状態の個数が閾値に達したら前状態が確定するとき。
四近傍の確定countだけを持ち、全cellを一度だけactivateする。
問題固有の要素
Aokiが禁止できる方向が一つなので通常の最短路のminimumではなくsecond minimumになり、逆探索では必要な確定neighbor数がちょうど2になる。
別の問題へ持ち帰る視点: 相手が最大b個の行動を潰すreachability gameでは、(b+1)番目の後続値と確定後続数b+1によるretrograde解析を検討する。
正当性
Aokiが一方向を禁止しTakahashiが残り最良を選ぶので非goalの値は隣接値の二番目+1。小さい値順に二隣接が確定した時、その二つへはどちらか一つを必ず選べるため有限上界が得られる。それより小さい値での確定が不可能なのは、その時点で小さい確定値が二つ揃っていないため。goal0から帰納的に最小有限値を確定する。最後まで未確定の領域は各点に有限値側の隣接が高々一つで、Aokiがそれを禁止し永久に閉じ込められる。
実装上の注意
- goalは隣接countに関係なくdist0で一度だけqueueへ入れる。盤外をneighborとして数えず、同じuを二重確定しない。dist総和は64 bitを使う。
復習の核
- cornerにgoal一個、boundaryの一本道、二方向だけgoalへ近づけるcell、到達不能領域を小盤面のvalue iterationと比較する。
計算量と制約
時間
H×W セル、K goal。各セルを一回確定し各隣接辺を定数回処理して O(HW+K)。
空間
距離、確定済み隣接数、queueで O(HW)。
制約との対応
公式制約の確認範囲: Time limit: 2.5 sec; Memory limit: 1024 MiB; Constraints: 2 \leq H \leq 3000; 2 \leq W \leq 3000; 1 \leq K \leq \min(HW,3000); 1 \leq R_i \leq H; 1 \leq C_i \leq W; (R_i,C_i) \neq (R_j,C_j) (1 \leq i < j \leq K); All input values are integers.
出典