Day 099-Q5 | Zobrist Hashing（盤面差分XORハッシュ）

問題

$N\times N$ の盤面があり、各マスには「空」または $K$ 種類のいずれかの駒が置かれる。最初はすべてのマスが空である。

$Q$ 回の操作を順に行う。$i$ 回目は「マス $(x_i,y_i)$ に駒の種類 $t_i$ を置く（$t_i=0$なら空にする）」。各操作直後の盤面全体の状態が、これまでに一度でも出現した状態（初期状態を含む）と完全に一致するかを判定し、一致するなら Yes、しないなら No を出力せよ。

$N,Q$が大きいため、毎回$O(N^2)$の全盤面比較は不可。Zobrist Hashingで各操作を$O(1)$（ハッシュテーブル操作を除く）で更新し、ハッシュ値の集合で一致判定せよ。

入力形式

N K Q
x_1 y_1 t_1
:
x_Q y_Q t_Q

制約

$1 \le N \le 1000$

$1 \le K \le 8$

$1 \le Q \le 2\times10^5$

$0 \le t_i \le K$（0は空にする）

入出力例

入力例1

出力例1

No
Yes
Yes
No

1手目: (1,1)に駒1 → 初出現 → No。2手目: (1,1)を空に → 初期状態と一致 → Yes。3手目: 再び(1,1)に駒1 → 1手目終了時と同じ → Yes。4手目: (2,2)に駒2（(1,1)はまだ駒1）→ 新状態 → No。

概念図

ヒント（段階的開示）

ヒント1: 方向性

盤面全体を毎回比較するのではなく、「盤面の状態」を1つの整数値（ハッシュ値）に圧縮し、その整数値だけを比較すれば高速に一致判定ができないか考えよ。ただしハッシュ値は「盤面を1マスずつ更新するたびに、差分だけで再計算」できる必要がある。

ヒント2: アプローチ

各「マスと駒の種類の組」$(x,y,t)$にランダムな整数キーを1つずつ割り当てる。盤面のハッシュ値を「現在置かれているすべての駒についてkeyをXORした値」と定義すると、駒を変える操作は「古いkeyをXORで除去し、新しいkeyをXORで追加」だけで更新できる（XORは自身の逆演算）。あとは出現済みハッシュ値の集合をsetで管理する。

ヒント3: 誘導（コード骨格）

rng = random.Random(12345)
key_cache = {}
def key(x, y, t):
    k = (x, y, t)
    if k not in key_cache:
        key_cache[k] = rng.getrandbits(64)
    return key_cache[k]

board = {}
h = 0
seen = {0}

old_t = board.get((x, y), 0)
if old_t != 0:
    h ^= key(x, y, old_t)
if t != 0:
    h ^= key(x, y, t)
    board[(x, y)] = t
else:
    board.pop((x, y), None)

print("Yes" if h in seen else "No")
seen.add(h)

模範解答 (Python)

import sys
import random


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    k = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1

    rng = random.Random(12345)
    key_cache = {}

    def key(x, y, t):
        kk = (x, y, t)
        v = key_cache.get(kk)
        if v is None:
            v = rng.getrandbits(64)
            key_cache[kk] = v
        return v

    board = {}
    h = 0
    seen = {0}
    out = []

    for _ in range(q):
        x = int(data[idx]); idx += 1
        y = int(data[idx]); idx += 1
        t = int(data[idx]); idx += 1

        old_t = board.get((x, y), 0)
        if old_t != 0:
            h ^= key(x, y, old_t)
        if t != 0:
            h ^= key(x, y, t)
            board[(x, y)] = t
        else:
            board.pop((x, y), None)

        out.append("Yes" if h in seen else "No")
        seen.add(h)

    print('\n'.join(out))


solve()

計算量: 1操作あたり平均$O(1)$（辞書・集合操作）、全体$O(Q)$。衝突確率は64ビットキーなら実用上無視できる。

Step-by-Step 解説

1盤面状態を1つの整数にまとめる発想
非空マスの(x,y,t)集合を、ランダムキーのXORで1つの整数に圧縮する。

2キーの遅延生成
実際に使われた(x,y,t)だけ初回アクセス時に乱数を生成しキャッシュすることで$O(Q)$個で済む。

3差分更新のロジック
古い駒のkeyをXORで除去し、新しい駒のkeyをXORで追加する。$a\oplus a=0$の性質が正しさの根拠。

4出現済み判定
seenにこれまでの全時点のハッシュ値を記録し、現在値が含まれるか調べる。

5計算量と衝突確率
1操作$O(1)$平均で全体$O(Q)$。64ビットキーなら衝突確率は$Q\le2\times10^5$程度では無視できるほど小さい（囲碁の劫・チェスの反復判定と同じ手法）。

よくあるミス

ミス	原因	正しい書き方
空マスにも固定キーを割り当ててXORに含める	大多数のマスが常に空で計算量・実装が煩雑になる	空マスは寄与ゼロとし、非空マスの集合だけで状態を表現する
`old_t`取得前に`board`を更新	更新後に取得すると常に新しい値になり古い寄与を除去できない	必ず`board.get((x,y),0)`で古い値を先に読む
浮動小数点乱数をキーに使う	XORでの厳密な相殺ができない	整数キー（`getrandbits(64)`等）を使う
初期状態（全マス空）を`seen`に入れ忘れる	「全部空に戻る」操作で誤ってNoと判定してしまう	`seen = {0}`としてハッシュ0を最初から登録する

次のステップ

発展: 千日手・劫（コウ）判定ルールの実装、盤面の回転・反転を同一視する正規化ハッシュ
次回予告: （新テーマローテーションへ継続）

自己評価

完全理解おおむね理解要復習

Day 099-Q5 — Zobrist Hashing（盤面差分XORハッシュ・重複状態検出）

問題