デンソークリエイトプログラミングコンテスト2025（AtCoder Beginner Contest 413）E,F,G問題メモ

デンソークリエイトプログラミングコンテスト2025（AtCoder Beginner Contest 413）

全完しやすい回。

E - Reverse 2^i

• $(1,2,3,\ldots,2^{N})$ の順列 $P=(P_0,P_1,\ldots,P_{2^{N}-1})$ が与えられます。
• あなたは次の操作を何回でも($0$ 回でもよい)行うことができます。
  • $0 \leq a \times 2^{b} \lt (a+1) \times 2^{b} \leq 2^{N}$ を満たす非負整数 $a,b$ を選び、$P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1}$ を反転する。ここで、$P_{a \times 2^{b}},P_{a \times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1}$ を反転するとは、$P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1}$ を $P_{(a+1) \times 2^{b}-1}, P_{(a+1) \times 2^{b}-2},\ldots,P_{a \times 2^{b}}$ に同時に置き換えることを意味する。
• 操作を繰り返して得られる $P$ のうち、辞書順最小のものを求めてください。
• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1 \leq T \leq 10^{5}$
• $1 \leq N \leq 18$
• $P$ は $(1,2,3,\ldots,2^{N})$ の順列
• 各入力ファイルについて、すべてのテストケースの $2^N$ の総和は $3 \times 10^{5}$ 以下
• 入力はすべて整数

こういう風なセグメント木のノードをイメージして、

|----------------------(1)----------------------|
|----------(2)----------|----------(3)----------|
|----(4)----|----(5)----|----(6)----|----(7)----|
|-(8)-|-(9)-|-(10)|-(11)|-(12)|-(13)|-(14)|-(15)|
| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16|

最下段の $1～16$ を $P$ の初期値として、操作は $(1)～(15)$ のいずれかの区間で反転操作をおこなうことに相当する。

たとえば(2)の区間内の要素と(3)の区間内の要素は、 最終形においてどちらかが前半分で、どちらかが後半分にならざるを得ない。
(2)の一部の要素だけと(3)の一部の要素だけを入れ替えるような操作はできない。
これは以降の段でも再帰的に同じことが言える。

適切に操作することで、$1$ は必ず先頭に持ってこられる。辞書順最小なので、これは最優先にしていい。

一方、$2$ は $1$ の後ろに持ってこられるとは限らない。
たとえば(3)の区間内に $1$、(2)の区間内に $2$ があった場合、 $1$ を先頭にするために(3)の方を前に持ってくると決めたら、$2$ は後半分にならざるを得ない。

以下のような再帰関数で、上から処理できる。

• $f(i,offset,width)$
  • $(i)$ の区間は、最終的に左から $offset$ ～ $offset+width$ の位置に配置することが分かっている。

前もって、$(1)～(15)$ の区間の最小値を計算しておく。

$width=1$ の場合、$Ans[offset] = P_i$ が確定する。

それ以外の場合、$(i)$ の2つの子 $l=2i,r=2i+1$ について、最小値を比較する。
$(l)$ の最小値 $\lt (r)$ の最小値 の時、$(l)$ を左に配置するとしてよい。以下を再帰的に呼び出す。

• $f(l,offset,width/2)$
• $f(r,offset+width/2,width/2)$

最初に $f(1,0,2^N)$ を呼び出すことで、全ての答えが $O(2^N)$ で求まる。

Python3

def solve(n, ppp):
    np2 = 1 << n
    table = [0] * (np2 << 1)
    table[np2:] = ppp
    for i in range(np2 - 1, 0, -1):
        table[i] = min(table[i * 2], table[i * 2 + 1])

    ans = [0] * np2

    def sub(l, r, offset, width):
        if table[l] > table[r]:
            l, r = r, l

        if width == 1:
            ans[offset] = table[l]
            ans[offset + 1] = table[r]
            return

        sub(l * 2, l * 2 + 1, offset, width >> 1)
        sub(r * 2, r * 2 + 1, offset + width, width >> 1)

    sub(2, 3, 0, np2 >> 1)

    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    ppp = list(map(int, input().split()))
    ans = solve(n, ppp)
    print(*ans)

F - No Passage

• $H$ 行 $W$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。
• このうち $K$ 個のマスはゴールになっています。$i$ 個目 $(1 \leq i \leq K)$ のゴールはマス $(R_i, C_i)$ です。
• 高橋君と青木君はこのグリッドとグリッドの上に置かれた $1$ つのコマを使ってあるゲームをしています。高橋君と青木君はコマがゴールのマスに到達するまで以下の一連の操作を繰り返し行います。
  • 青木君は 上下左右のうち、遮断する1方向を選ぶ。
  • その後、高橋君は青木君に遮断されなかった最大3方向から1方向を選んで、コマをその方向に隣接するマスに移動させる。

• 高橋君の目的はコマがゴールに到達するまでの移動回数を最小化することです。
• 青木君の目的はコマがゴールに到達しないようにすることであり、それが不可能な場合は移動回数を最大化することです。
• $1 \leq i \leq H,1 \leq j \leq W$ を満たすすべての整数の組 $(i,j)$ に対して以下の問題を解き、解の総和を求めてください。
  • コマがマス $(i,j)$ にある状態からゲームを始める。両者が各々の目的を目指して最適に行動するとき、高橋君がコマをゴールに到達させることができるのであれば移動回数の最小値、そうでないならば $0$ が解である。

• $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 \lt j \leq K$)
• 入力はすべて整数

青木君の遮断がなければ、ゴールから近い順に確定していく単純な多始点BFSの問題である。

青木君は最もゴールまでの操作回数が少ない方向を遮断する。
逆に言うと、高橋君は2番目に操作回数が少ない方向へは進める。

よって、多始点BFSをちょっと改良し、 「周囲（最大）4マスのうち、2番目に近い距離」が確定したら自身の距離も確定するとすればよい。

周囲のうち距離が確定したマス数を、BFSで追加で管理すればよい。

Python3

from collections import deque


def solve(h, w, k, goals):
    h2 = h + 2
    w2 = w + 2
    hw = h2 * w2
    INF = 1 << 60

    MOVE = (-w2, -1, 1, w2)

    dp1 = [INF] * hw
    dp2 = [INF] * hw
    for r, c in goals:
        i = r * w2 + c
        dp1[i] = 0
        dp2[i] = 0

    hq = deque()
    for r, c in goals:
        i = r * w2 + c
        for d in MOVE:
            if dp1[i + d] == INF:
                dp1[i + d] = 1
            elif dp2[i + d] == INF:
                dp2[i + d] = 1
                hq.append(i + d)

    while hq:
        i = hq.popleft()
        for d in MOVE:
            if dp1[i + d] == INF:
                dp1[i + d] = dp1[i] + 1
            elif dp2[i + d] == INF:
                dp2[i + d] = dp2[i] + 1
                hq.append(i + d)

    ans = 0
    for i in range(hw):
        if dp2[i] != INF:
            ans += dp2[i]

    return ans


h, w, k = map(int, input().split())
goals = [tuple(map(int, input().split())) for _ in range(k)]
ans = solve(h, w, k, goals)
print(ans)

G - Big Banned Grid

• $H$ 行 $W$ 列のマス目があります。
• $K$ 個のマス $(r _ 1,c _ 1),(r _ 2,c _ 2),\ldots,(r _ K,c _ K)$ には障害物が置かれています。
• 高橋くんははじめマス $(1,1)$ におり、上下左右に隣接する何も置かれていないマスに移動することを繰り返してマス $(H,W)$ へ行きたいと思っています。
• 高橋くんがマス $(1,1)$ からマス $(H,W)$ へ移動できるか判定してください。

• $1\le H\le2\times10 ^ 5$
• $1\le W\le2\times10 ^ 5$
• $0\le K\le2\times10 ^ 5$
• $1\le r _ i\le H\ (1\le i\le K)$
• $1\le c _ i\le W\ (1\le i\le K)$
• $(r _ i,c _ i)\ne(1,1)\ (1\le i\le K)$
• $(r _ i,c _ i)\ne(H,W)\ (1\le i\le K)$
• $(r _ i,c _ i)\ne(r _ j,c _ j)\ (1\le i\lt j\le K)$
• 入力はすべて整数

制約を見ると、$O(HW)$ の単純な経路探索はできないことがわかる。

ただ、$K$ が小さいので「障害物により盤面が分断されているか」は、$O(K)$ またはそれに近い計算量で求められる。

具体的には、「盤面の左端・下端を表す頂点」「盤面の右端・上端を表す頂点」を追加した $K+2$ 個の頂点を用意し、 Union-Findで周囲8方向に隣接した障害物の間を繋いでいって、上記の2つの頂点がくっついてしまったら分断されている。

Python3

from atcoder.dsu import DSU


def solve(h, w, k, objects):
    w2 = w * 2
    around = (-w2 - 1, -w2, -w2 + 1, -1, 1, w2 - 1, w2, w2 + 1)
    ld = k
    ur = k + 1
    dsu = DSU(k + 2)
    aaa = {}
    for oi, (r, c) in enumerate(objects):
        i = r * w2 + c
        aaa[i] = oi

        if r == 1:
            dsu.merge(oi, ur)
            # print(f'  merge {oi=} {ur=}')
        if r == h:
            dsu.merge(oi, ld)
            # print(f'  merge {oi=} {ld=}')
        if c == 1:
            dsu.merge(oi, ld)
            # print(f'  merge {oi=} {ld=}')
        if c == w:
            dsu.merge(oi, ur)
            # print(f'  merge {oi=} {ur=}')

    for i in aaa:
        oi = aaa[i]
        for d in around:
            if i + d not in aaa:
                continue
            oj = aaa[i + d]
            dsu.merge(oi, oj)
            # print(f'  merge {oi=} {oj=}')

    return not dsu.same(ld, ur)


h, w, k = map(int, input().split())
objects = [tuple(map(int, input().split())) for _ in range(k)]
ans = solve(h, w, k, objects)
if ans:
    print('Yes')
else:
    print('No')

今回は始点が $(1,1)$、終点が $(H,W)$ だったのでわかりやすいが、 バリエーションとして、任意の場合でも解ける。

|---------|■|------|
|-----|■■|--------|    |---|: 1つのノード
|---|■|--|■|------|
|---|■|----|■■|--|
|-----|■|--|■|----|

各行につき、障害物のない連続区間を1つのノードとする。
これをUnion-Findでつなぎ、始点の属するノードと終点の属するノードが同じになるかを確かめればよい。

ノードは高々 $O(H+K)$ 個しか作られない。

連続する2行でどのノードとどのノードが隣接しているかは、尺取法や二分探索などで求められる。