M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232) E,G,H問題メモ

M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)

E - Rook Path

問題

$H \times W$ の盤面の $(X_1,Y_1)$ にルーク（飛車）がいる
列または行が同じマス（列も行も同じマスは除く）に移動させることを繰り返す
ちょうど $K$ 回の移動後、$(X_2,Y_2)$ にいるような動かし方の個数を $\mod{998244353}$ で求めよ
$2 \le H,W \le 10^9$
$1 \le K \le 10^6$

解法

壁マスとかはないので移動には対称性があり、複数の行・列は一絡げにまとめて考えられる。

今どこにいようと、1回で移動可能なマスは $(H-1)+(W-1)$ 通りなので、例えば最終的にどこにいてもいい問題なら、単に $(H+W-2)^K$ 通りとなる。

ただしこの問題では最終的には $(X_2,Y_2)$ にいるかどうかが区別できないといけない。

よって、以下の4つの「状態」に分けておけばよい。

① $(X_2以外, Y_2以外)$ にいる
② $(X_2以外, Y_2)$ にいる
③ $(X_2, Y_2以外)$ にいる
④ $(X_2, Y_2)$ にいる

同じマスには移動できないことを踏まえて①～④の間の遷移を考えると、こんな感じになる。

移動元\先         ①   ②   ③  ④
    ①    (H-2)+(W-2)   1    1   0
    ②           W-1  H-2    0   1
    ③           H-1    0  W-2   1
    ④             0  H-1  W-1   0

①～④をグラフの頂点と見なして、移動元から移動先の頂点にそれぞれ上表の数だけ有向辺が張ったグラフを考える。
ルークを1回動かすことは、辺に沿って頂点を1回移動することと言い換えることができる。

上の表を隣接行列 $T$ とすると、$K$ 回の移動方法の個数は、$T^K$ で表現できる。

隣接行列で経路数を求める方法 | ユーホス.com

行列累乗で $O(\log{K})$ で $T^K$ を求めた後、 $(X_1,Y_1)$ が①～④のどれに当たるかによって、それ→④への経路数が答え。

Python3

import numpy as np

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
MOD = 998244353

transition = np.array([
    [h + w - 4, 1, 1, 0],
    [w - 1, h - 2, 0, 1],
    [h - 1, 0, w - 2, 1],
    [0, h - 1, w - 1, 0],
], np.int64)


def mod_pow(x, a, MOD):
    ret = np.identity(4, np.int64)
    cur = x
    while a:
        if a & 1:
            ret = ret @ cur % MOD
        cur = cur @ cur % MOD
        a >>= 1
    return ret


transition = mod_pow(transition, k, MOD)

ans = transition[((x1 == x2) << 1) | (y1 == y2), 3]
print(ans)

G - Modulo Shortest Path

問題

$N$ 個の正整数列 $(A_1,...,A_N)$ と $(B_1,...,B_N)$ と正整数 $M$ が与えられる
$N$ 頂点の有向完全グラフを考える
辺 $i→j$ のコストは、$(A_i+B_j)$ を $M$ で割ったあまりである
頂点 $1$ から $N$ への最短距離を求めよ
$2 \le N \le 2 \times 10^5$
$2 \le M \le 10^9$
$0 \le A_i,B_i \lt M$

解法

愚直にやると $O(N^2)$ 本の辺ができてしまうので無理。辺のコストが規則的なことを使うしかない。

$A_i+B_j$ は $2M$ を超えることはないので、

$M$ を超えたら $A_i+B_j-M$
$M$ を超えないなら $A_i+B_j$

となる。$A_i$ を固定すると、$B_j$ が $M-A_i$ 以上かどうかが分水嶺となる。

なので、まぁ類題を解いたことがないとなかなかひらめくのは難しい気がするが、頂点を $A$ 側と $B$ 側の2種類に分けた上で、

サンプル1
Ai  10  11   6   0
 i  ①  ②  ③  ④
 
 j  ④→③→②→①
Bj   1   4   7   8

$B_j$ を昇順に並び替え、小さい順に次の頂点へ辺を張っていく。

$A$ 側の頂点 $A_s$ から、和が $M$ を超える最小の $B$ 側の頂点 $B_t$ へと辺を張ると、 $B_t$ から移動できる $B$ 側の頂点は（自身より大きい頂点にしか移動できないので）全て $A_s$ との和が $M$ 以上となる。

なので、

$A_s→B_t$ に、コスト $A_s+B_t-M$ の辺を張る
$A_s→(Bの最小の頂点)$ に、その和のコストの辺を張る

としてやると、相手によってコストが変化する問題を上手く表現できる。

そして、$B側の①→A側の①$ のように $A$ 側の同じ頂点に戻る辺も張ってやると、その辺を使って戻った頂点が、元のグラフで実際に次に移動する頂点となる。

（※オレンジ線の真ん中のコストは3の間違い）

ただし、$A_i$ によっては青の辺は存在しないこともある。

このグラフでDijkstraをすれば、$2N$ 頂点 $4N$ 辺なので、間に合う。

Python3

from bisect import bisect_left
from heapq import heappop, heappush


def dijkstra(s, t, links):
    q = [s]
    mask = (1 << 19) - 1
    INF = 1 << 60
    costs = [INF] * len(links)
    costs[s] = 0
    while q:
        cost_v = heappop(q)
        cost = cost_v >> 19
        v = cost_v & mask
        if v == t:
            return cost
        if cost > costs[v]:
            continue
        costs[v] = cost
        for u, c in links[v]:
            new_cost = cost + c
            if new_cost >= costs[u]:
                continue
            costs[u] = new_cost
            heappush(q, (new_cost << 19) | u)


n, m = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))

bis = sorted((b, i) for i, b in enumerate(bbb))
sorted_bbb = [bi[0] for bi in bis]

links = [set() for _ in range(n * 2)]
for i, a in enumerate(aaa):
    j = bisect_left(sorted_bbb, m - a)
    if j < n:
        links[i].add((n + j, a + sorted_bbb[j] - m))
    if j > 0:
        links[i].add((n, a + sorted_bbb[0]))
    links[n + i].add((bis[i][1], 0))

    if i > 0:
        links[n + i - 1].add((n + i, sorted_bbb[i] - sorted_bbb[i - 1]))

ans = dijkstra(0, n - 1, links)
print(ans)

H - King's Tour

問題

$H \times W$ の盤面の左上 $(1,1)$ に、周囲8マスに動けるキング（王将）がいる
全てのマスを1回ずつ経由して $(a,b)$ で移動を終えるようなルートを1つ構築せよ
$2 \le H,W \le 100$

解法

E問題に続きチェス問題。

時間をかければひたすら場合分けすることで気合いで通すことはできそうだが、いかに速く実装できるか、が本質と見た方がよさそう。

周囲8マスに移動できるのは自由度が高くて、適当に移動して多少変な形に残ったとしても、（完全に分断されなければ）なんなりと埋めることはできそう。

貪欲を試してみる。

最初に適当に、$(1,1)→(a,b)$ への（全てのマスを通過しなくてもよい）パスを作る
パス中にマス $C_1→C_2$ に移動する瞬間があったとして、その両方に隣接するマス $C_3$ がまだ未経由なら、$C_1→C_3→C_2$ に張り替える
全てのマスを経由するまで上を繰り返す

やってみると、サイズが小さいときにWAが出た。

どうも、幅が $2～3$ マスで細長い時にゴールより向こう側に移動できなかったり、$a=2,b=W$ などの時に隅に1マスだけ余りがちらしい。

上手くいくかどうかは、最初の $(1,1)→(a,b)$ へのパスの作り方、複数の未経由の $C_3$ があったときにどれを優先するか、によっても変わってくる。

途中で不可能に陥ったら一旦破棄して、最初のパスを決める際にまず $(H,W)$ まで移動して、そこから $(a,b)$ に戻るものを初期状態とすることで、上手くいった。
必ず上手くいく証明はしてない。

やってることは単純なはずなのに、できあがる経路は結構キモい。

未経由の $C_3$ が複数あったときの優先順位を変えるとガラッと変わって綺麗になったりして面白い。

Python3

def try_update(ans, i, j, mi, mj):
    if ans[mi][mj] is None:
        ans[mi][mj] = ans[i][j]
        ans[i][j] = (mi, mj)
        return True
    return False


def init(ans, h, w, a, b, pattern):
    if pattern == 0:
        for i in range(1, a + 1):
            ans[i - 1][0] = (i, 0)
        for j in range(1, b + 1):
            ans[a][j - 1] = (a, j)
    elif pattern == 1:
        for j in range(1, b + 1):
            ans[0][j - 1] = (0, j)
        for i in range(1, a + 1):
            ans[i - 1][b] = (i, b)
    elif pattern == 2:
        for i in range(1, h):
            ans[i - 1][0] = (i, 0)
        for j in range(1, w):
            ans[h - 1][j - 1] = (h - 1, j)
        for i in range(h - 2, a - 1, -1):
            ans[i + 1][w - 1] = (i, w - 1)
        for j in range(w - 2, b - 1, -1):
            ans[a][j + 1] = (a, j)
    else:
        for j in range(1, w):
            ans[0][j - 1] = (0, j)
        for i in range(1, h):
            ans[i - 1][w - 1] = (i, w - 1)
        for j in range(w - 2, b - 1, -1):
            ans[h - 1][j + 1] = (h - 1, j)
        for i in range(h - 2, a - 1, -1):
            ans[i + 1][b] = (i, b)
    ans[a][b] = (-1, -1)


def expand(ans, h, w, a, b):
    i = 0
    j = 0
    count = 0

    while i != a or j != b:
        ni, nj = ans[i][j]
        if i == ni:
            if i > 0 and try_update(ans, i, j, i - 1, j):
                continue
            if i < h - 1 and try_update(ans, i, j, i + 1, j):
                continue
            if i > 0 and try_update(ans, i, j, i - 1, nj):
                continue
            if i < h - 1 and try_update(ans, i, j, i + 1, nj):
                continue
        elif j == nj:
            if j > 0 and try_update(ans, i, j, i, j - 1):
                continue
            if j < w - 1 and try_update(ans, i, j, i, j + 1):
                continue
            if j > 0 and try_update(ans, i, j, ni, j - 1):
                continue
            if j < w - 1 and try_update(ans, i, j, ni, j + 1):
                continue
        else:
            if try_update(ans, i, j, ni, j):
                continue
            if try_update(ans, i, j, i, nj):
                continue
        count += 1
        i = ni
        j = nj

    count += 1
    return count


def print_ans(ans, a, b):
    i, j = 0, 0
    while i != a or j != b:
        print(i + 1, j + 1)
        i, j = ans[i][j]
    print(a + 1, b + 1)


def solve(h, w, a, b):
    a -= 1
    b -= 1

    for pattern in range(4):
        ans = [[None] * w for _ in range(h)]

        if pattern == 2 and (a == h - 1 or b == 0):
            continue
        if pattern == 3 and (a == 0 or b == w - 1):
            continue

        init(ans, h, w, a, b, pattern)

        if expand(ans, h, w, a, b) != h * w:
            continue

        print_ans(ans, a, b)

        break
    else:
        raise


h, w, a, b = map(int, input().split())
solve(h, w, a, b)

目次

M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232) E,G,H問題メモ

E - Rook Path

問題

解法

G - Modulo Shortest Path

問題

解法

H - King's Tour

問題

解法