DEGwer さんの D 論応援コンテスト B問題メモ

B - vs. DEGwer

問題

$H \times W$ のグリッド上に部屋が並んでいる
- 上下左右に隣接する部屋の間に扉があり、互いに繋がっている
- 一番左列の部屋の左側にそれぞれ扉があり、入口となる大部屋 $S$ に繋がっている
- 一番右列の部屋の右側にそれぞれ扉があり、出口となる大部屋 $T$ に繋がっている
- はじめ、全ての扉は未固定
あなたと魔王でゲームをする
- 先攻・後攻の情報が与えられる
- 先攻から、以下を交互に繰り返す
  - あなたは未固定の扉を1つ選び、開いた状態で固定する
  - 魔王は未固定の扉を1つ選び、閉じた状態で固定する
- $S$ から $T$ に、開いた状態の扉のみを通して移動できることが確定すればあなたの勝ち
- 移動できないことが確定すればあなたの負け
$H,W$ と、どちらが先攻かの情報が与えられた時点で、あなたが勝利可能か判定せよ
勝利可能な場合、実際にジャッジとインタラクティブにゲームをして勝利せよ
$1 \le H,W \le 20$

例

  |   |   |     (H,W)=(3,2) の盤面、
   --- ---
S |   |   | T   「|」および「---」が扉（計13個）
   --- ---
  |   |   |

解法

前提知識と必勝条件

「シャノンのスイッチングゲーム」と呼ばれるゲームの一種である。
特にこのようなグリッド状に限定したものを指して、Galeのゲームや Bridg-it とも呼ぶらしい。

Shannon Switching Game (Gale, Bridg-it) - Complexity of Games

各部屋と $S,T$ を頂点、扉を辺と見なす。
あなたは辺を固定し、魔王は辺を削除して、$S$ と $T$ を連結にできればあなたの勝ちとなる。

ゲームの必勝法として、グラフから「辺疎な（辺を共有しない）全域木を2つ取る」ことができれば、後攻であっても、必ず全ての頂点を連結にできる。
当然 $S,T$ も連結にできるので、勝利する。

全域木A
①--②--③-|-④--⑤--⑥    片方の全域木に属する辺が切られたときでも、

全域木B
     ,-------,,------,     もう一方の全域木はまるごと残っている。
①  ②  ③   ④  ⑤  ⑥    こっちの方で、分かれた成分同士を
|`------'`-------'   |     結ぶような辺（たとえば②-④）を選ぶことで
`--------------------'     

全域木A
①--(②④)--⑤--⑥         縮約したグラフでは、辺を共有しない全域木が2つある状態を維持できる
③--'

全域木B
⑤--③--①--⑥--(②④)

これを繰り返すと、全ての頂点が1つになるまで縮約（＝全体を連結に）できることが示せる。

ただし、全域木が2つ取れないからといって、必敗とは限らないので注意。

勝利可能判定

さて、問題のグラフで辺は $H \times (W+1) + (H-1) \times W=2HW+H-W$ 本ある。
一方、頂点は $HW+2$ 個で、2つの全域木に必要な辺数は $2HW+2$ 本である。

少なくとも、$2HW+H-W \ge 2HW+2$、つまり $H \ge W+2$ であることが必要となる。

では、$H \ge W+2$ なら構成できるのか？

以下のようにすると、必ず構成できる。

   A   B   A   B      (H,W) = (5,3)
    -A- -B- -A-       Aだけの扉（を辺と見立てたグラフ）も、
   B   A   B   A      Bだけの扉も、全域木を構成する
    -B- -A- -B-
S  A   B   A   B  T
    -A- -B- -A-
   B   A   B   A
    -B- -A- -B-
   A   B   A   B

また、$H = W+1$ の時、辺が1本だけ足りないのだが、

   A x B x A x B      (H,W) = (4,3)
    -A- -B- -A-
   B o A x B x A      Aは全域木となっているが、
o   -B- -A- -B-   x   Bが1本だけ足りず、完全には繋がらず
   A o B o A x B      o成分とx成分の2つに分かれている
    -A- -B- -A-
   B o A o B o A

先攻の場合、この2成分を初手で縮約する（たとえば左上の -A- を選ぶ）ことで、必勝法に持ち込める。

よって、「$H \ge W+2$」または「$H = W+1$ かつあなたの先攻」の場合、勝利できる。

では、他の場合は必ず敗北するのか？
結論から言うと敗北する。以下、それを示す。

魔王からしてみると、扉の連結点を頂点と見立て、これを閉じた扉によって上から下まで繋げることができれば、阻止が成功したと言える。

 ___ S___
/  /  \  \
|  |  |  |    (H,W) = (3,3)
o--o--o--o
|  |  |  |
o--o--o--o
|  |  |  |
\  \  /  /
 ~~~ T ~~

魔王にとっての必勝法も、このグラフから2つの全域木が取れればよいということになる。

全域木の構築の仕方もあなたの場合と同様にでき、結局、「$H \le W$」または「$H = W+1$ かつ魔王の先攻」なら、魔王の必勝ということになり、ちょうどあなたの場合を逆にした条件であることが分かる。

実装

勝利可能で実際にゲームを行う場合、$H,W$ が小さいので、愚直にUnion-Findなどで連結判定を毎回やってよい。

「2つの全域木」を取ろうとすると、$H \ge W+3$ の時に辺があまりややこしいので、木でなくなってもよいので上述のナナメ状に、辺を2つのグループA,Bに分ける。

相手がAに属する辺を削除してきたら、（既に固定済みの辺）+（未確定のAの辺）をUniteした後、

全体が連結なら、適当に選んでよい（AとBの数の平衡を保つため、Bの方から適当に選んで固定する）
2つに分かれているなら、Bから、両端が別々の連結成分に属する未確定の辺を探し、それを固定する

Python3

class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def save(self):
        self.saved = self.table.copy()

    def restore(self):
        self.table = self.saved

    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return False
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1
        return True

    def get_size(self, x):
        return -self.table[self.root(x)]


def check(spt0, uft0: UnionFind, spt1):
    uft0.save()
    for u, v in spt0:
        uft0.unite(u, v)

    roots = [u for u, val in enumerate(uft0.table) if val < 0]
    if len(roots) == 1:
        uft0.restore()
        if len(spt0) > len(spt1):
            return next(iter(spt0))
        else:
            return next(iter(spt1))

    for u, v in spt1:
        if not uft0.find(u, v):
            uft0.restore()
            return (u, v)


h, w, move = input().split()
h = int(h)
w = int(w)

if h <= w:
    print('No')
    exit()

if h == w + 1 and move == 'Second':
    print('No')
    exit()

print('Yes')

n = h * w + 2
s = h * w
t = s + 1
spt = [set(), set()]
uft = [UnionFind(n), UnionFind(n)]
for i in range(h):
    b = i & 1
    spt[b].add((s, i * w))
    b ^= 1
    for j in range(w - 1):
        spt[b].add((i * w + j, i * w + j + 1))
        b ^= 1
    spt[b].add(((i + 1) * w - 1, t))
    if i < h - 1:
        b = (i & 1)
        for j in range(w):
            spt[b].add((i * w + j, (i + 1) * w + j))
            b ^= 1

if move == 'First':
    print('- 1 1')
    uft[0].unite(0, w)
    uft[1].unite(0, w)
    spt[0].discard((0, w))
    spt[1].discard((0, w))

while True:
    op, di, dj = input().split()
    if op == 'a' or op == 'w':
        break

    di = int(di) - 1
    dj = int(dj) - 1
    if op == '|':
        if dj == 0:
            closed = (s, di * w)
        elif dj == w:
            closed = ((di + 1) * w - 1, t)
        else:
            closed = (di * w + dj - 1, di * w + dj)
    else:
        closed = (di * w + dj, (di + 1) * w + dj)

    if closed in spt[0]:
        spt[0].remove(closed)
        u, v = opened = check(spt[0], uft[0], spt[1])
    else:
        spt[1].remove(closed)
        u, v = opened = check(spt[1], uft[1], spt[0])

    if u == s:
        print(f'| {v // w + 1} 1')
    elif v == t:
        print(f'| {u // w + 1} {w + 1}')
    elif u + w == v:
        i, j = divmod(u, w)
        print(f'- {i + 1} {j + 1}')
    else:
        i, j = divmod(u, w)
        print(f'| {i + 1} {j + 2}')

    uft[0].unite(u, v)
    uft[1].unite(u, v)
    spt[0].discard(opened)
    spt[1].discard(opened)

目次

DEGwer さんの D 論応援コンテスト B問題メモ

B - vs. DEGwer

問題

例

解法

前提知識と必勝条件

勝利可能判定

実装