大通りなら $1$ 秒で移動できる距離を $10^9$ 秒 $=31.7$ 年かかる道路がそこら中にある街とは一体……。
場合分けをちゃんとやれば解ける。考え方自体はそんな高度なアルゴリズムの知識を要するものでもない。
基本は大通りを使うのが間違いない。
実用上の経路探索でも、大真面目に全ての道路を等価値に扱っていると時間かかるので、
高速道路や国道など速く移動できる道路(*)とそうでないものを分け、
(*)に到達したらそこからは(*)のみを使って探索するのはよくある手法。
起点と終点が近くて大通りに出ない方が速い場合もあるので、 それはマンハッタン距離 $|S_x-G_x|+|S_y-G_y|$ の $K$ 倍として、上限を出しておく。
それ以外は、まず大通りまで出ることを考える。
起点と終点から、上下左右にまっすぐ大通りに出る $4 \times 4 = 16$ 通りそれぞれについて試す。
大通りに出た座標を $(S_x',S_y'), (G_x', G_y')$ とすると、大体の場合はこのマンハッタン距離で移動できる。
ただし、
のいずれかの場合は、コの字型に迂回しないといけない場合がある。
出た大通りが一緒だったり、区画が異なる行や列だった場合は大丈夫なので、この条件設定を見つけるのがやや難しい。
.■■■ ■■■ ■■■ ■■■ ■■■ ■■■. ■■■ ■■■ ■■■
上例なら、上に出るのか下に出るのかで2通り試す。
また、($K$ が整数の制約では実は必ず迂回した方が良いっぽいのだが、) 迂回せず、そのまま突っ切った方が良いことも考えられるので、それも試す。
DPで、規則的で高速化できる多数の遷移と、不規則な少数の遷移。
禁止されているのが累積和なので、累積和で考える。
奇数しか置けないので、累積和では奇数の後は必ず偶数、偶数の後は必ず奇数となる。
とりあえずまずは禁止値がないとして実験すると、
i (0) 1 2 3 4 5 6 7 8 ... f(i) 1 1 1 2 3 5 8 13 21 ... `-->---`-->--`->--`->'
たとえば $f(8)$ は、前の総和が奇数の箇所から遷移できるので、$f(7)+f(5)+f(3)+f(1)$ となる。
ここで、2個前の $f(6)=f(5)+f(3)+f(1)$ なので、結局 $f(8)=f(7)+f(6)$ と置き換えることができ、フィボナッチ数列が現れる。
では、禁止値があるとどうなるかというと、
x i (0) 1 2 3 4 5 6 7 8 9 10 ... f(i) 1 1 1 2 3 0 3 8 11 19 30 ... x x i (0) 1 2 3 4 5 6 7 8 9 10 ... f(i) 1 1 1 2 3 0 0 5 8 13 21 ... x x i (0) 1 2 3 4 5 6 7 8 9 10 ... f(i) 1 1 1 2 3 0 3 0 3 11 14 ...
禁止値の配置によって挙動は異なるものの、乗り越えた後はまたフィボナッチのように前項2つの和となっていく。
$i-2$ が禁止値でないなら、$f(i-2)$ が 「禁止値とか全て考慮した上での $f(i-3)+f(i-5)+f(i-7)+...$」を表すので、 $f(i)=f(i-1)+f(i-3)+...$ を求めるときにそれをそのまま活用できる。
そして、フィボナッチ(のような遷移)であれば、行列累乗により $M$ 項目を $O(\log{M})$ で求められるので、高速化できる。
$$ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) ^ {M-2} \left( \begin{array}{c} 1 \\ 1 \end{array} \right) $$
問題は、禁止値の乗り越え方だが……
禁止値でフィボナッチが崩れるのは、$f(i)$ が強制的に $0$ にされてしまい、 より後の $f(i+2)=f(i+1)+f(i-1)+...$ などを求める際に $f(i-1)+f(i-3)+...$ を代替できなくなるからである。
なら、$f(i)$ とは別に、それはそれで引き継いでやればよい。
$g$ は1個前の値まで必要なので、$f(i),g(i),g(i-1)$ の3つの値を管理しておけばよい。
x x i (0) 1 2 3 4 5 6 7 8 9 ... f(i) 1 1 1 2 3 0 3 0 3 11 ... f(i) が0になっても、 g(i) 0 1 1 2 3 [5] 3 [8] 3 11 ... g(i) でちゃんとそれまでの g(i-1) 0 0 1 1 2 3 5 3 8 3 ... 累積和を持ってるので更新できる
禁止値でない部分の $m$ 個先までの遷移は以下のようになるので、
$$ \left( \begin{array}{c} f(x+m) \\ g(x+m) \\ g(x+m-1) \end{array} \right) = \left( \begin{array}{ccc} 1 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{array} \right) ^ {m} \left( \begin{array}{c} f(x) \\ g(x) \\ g(x-1) \end{array} \right) $$
最大 $N+1$ 回の、禁止値同士の間の行列累乗による高速な遷移と、 $N$ 回の禁止値の愚直な遷移を行えば、$O(N\log{S})$ で求められる。
x x x i (0) ... A1-1 A1 ... A2-1 A2 A3 ... S |-------->|->|--------->|-->|-->|------->| 行列累乗 愚直 行列累乗 愚直 愚直 行列累乗