AtCoder Beginner Contest 258 F,Ex問題メモ

F - Main Street

問題

$xy$ 平面と見なせる碁盤目状の道路がある
- 全ての整数 $k=...,-2,-1,0,1,2,...$ に対して、$x=k$ および $y=k$ に道路がある
- そのうち、$B$ ごとに「大通り」がある（$x=Bk$ および $y=Bk$）
交差点 $(x,y)$ から東西南北に1区画隣の交差点に移動するのに、大通りは $1$ 秒、それ以外の道路は $K$ 秒かかる
$(S_x,S_y)$ から $(G_x,G_y)$ に移動するのにかかる最短時間を求めよ
$T$ ケース与えられるので、それぞれについて答えよ
$1 \le T \le 2 \times 10^5$
$1 \le B,K,起終点座標 \le 10^9$

解法

大通りなら $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$ が整数の制約では実は必ず迂回した方が良いっぽいのだが、）迂回せず、そのまま突っ切った方が良いことも考えられるので、それも試す。

Python3

t = int(input())
for _ in range(t):
    b, k, sx, sy, gx, gy = map(int, input().split())

    slx = sx // b * b
    srx = slx + b
    sly = sy // b * b
    sry = sly + b
    glx = gx // b * b
    grx = glx + b
    gly = gy // b * b
    gry = gly + b

    manhattan = (abs(sx - gx) + abs(sy - gy)) * k

    spos = [(slx, sy, sly), (srx, sy, sly), (sx, sly, slx), (sx, sry, slx)]
    gpos = [(glx, gy, gly), (grx, gy, gly), (gx, gly, glx), (gx, gry, glx)]

    # [左, 右, 下, 上] の大通りに出るまでの距離
    st = [sx - slx, srx - sx, sy - sly, sry - sy]
    gt = [gx - glx, grx - gx, gy - gly, gry - gy]

    ans = manhattan

    for sp in range(4):
        x1, y1, z1 = spos[sp]
        for gp in range(4):
            x2, y2, z2 = gpos[gp]

            to_street = (st[sp] + gt[gp]) * k
            street_manhattan = abs(x1 - x2) + abs(y1 - y2)
            tmp = 0

            if sp >> 1 == gp >> 1 and z1 == z2:
                if sp >> 1 == 0 and x1 != x2:
                    tmp = to_street + min(
                        abs(x1 - x2) + min(st[2] + gt[2], st[3] + gt[3]),
                        abs(x1 - x2) * k + abs(y1 - y2),
                    )
                elif sp >> 1 == 1 and y1 != y2:
                    tmp = to_street + min(
                        abs(y1 - y2) + min(st[0] + gt[0], st[1] + gt[1]),
                        abs(y1 - y2) * k + abs(x1 - x2),
                    )
                else:
                    tmp = to_street + street_manhattan
            else:
                tmp = to_street + street_manhattan

            ans = min(ans, tmp)

    print(ans)

Ex - Odd Steps

問題

以下の条件を満たす数列の個数を $\mod{998244353}$ で求めよ
条件
- 各項は全て正の奇数
- 総和は $S$
- $N$ 個の禁止値 $A_1,...,A_N$ が決められており、先頭から累積和を取ったとき、これらのいずれも出現しない
$1 \le N \le 10^5$
$1 \lt S \le 10^{18}$

解法

DPで、規則的で高速化できる多数の遷移と、不規則な少数の遷移。

禁止されているのが累積和なので、累積和で考える。
奇数しか置けないので、累積和では奇数の後は必ず偶数、偶数の後は必ず奇数となる。

$f(x)=$ 総和が $x$ となる、条件を満たす数列の個数

とりあえずまずは禁止値がないとして実験すると、

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(x) = f(x-1)+f(x-3)+...$ の総和

$i+1$ が禁止値でない
- $f(i+1)=g(i+1)=f(i)+g(i-1)$
$i+1$ が禁止値
- $f(i+1)=0$
- $g(i+1)=f(i)+g(i-1)$

$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
       |-------->|->|--------->|-->|-->|------->|
        行列累乗 愚直 行列累乗 愚直 愚直 行列累乗

Python3

import os
import sys

import numpy as np


def solve(inp):
    MOD = 998244353

    def matmul(a, b, n):
        c = np.zeros_like(a)
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    c[i, k] += a[i, j] * b[j, k]
        return c % MOD

    def mod_pow(a):
        ret = np.eye(3, dtype=np.int64)
        cur = np.zeros((3, 3), dtype=np.int64)
        cur[0, 0] = cur[0, 2] = cur[1, 0] = cur[1, 2] = cur[2, 1] = 1
        while a:
            if a & 1:
                ret = matmul(ret, cur, 3)
            cur = matmul(cur, cur, 3)
            a >>= 1
        return ret

    n = inp[0]
    s = inp[1]
    aaa = inp[2:]

    f = 1
    g = 0
    h = 0
    i = 0
    for a in aaa:
        res = mod_pow(a - i - 1)
        _f = (f * res[0, 0] + g * res[0, 1] + h * res[0, 2]) % MOD
        _g = (f * res[1, 0] + g * res[1, 1] + h * res[1, 2]) % MOD
        _h = (f * res[2, 0] + g * res[2, 1] + h * res[2, 2]) % MOD
        f, g, h = 0, (_f + _h) % MOD, _g
        i = a

    res = mod_pow(s - i)
    ans = (f * res[0, 0] + g * res[0, 1] + h * res[0, 2]) % MOD
    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

目次

AtCoder Beginner Contest 258 F,Ex問題メモ

F - Main Street

問題

解法

Ex - Odd Steps

問題

解法