feature image

2022年5月14日 | ブログ記事

集合をハッシュする (Zobrist hashing)

Zobrist hashing とは

https://en.wikipedia.org/wiki/Zobrist_hashing

チェスをするコンピュータを作るときにチェスの状態をハッシュするために Zobrist さんが作ったハッシュ方法らしいです。

できること

やり方

  1. 集合の要素として出てくる値にランダムな整数を割り当てます。
  2. 集合のハッシュは、その集合の各要素に割り当てられた整数の総 XOR です。

1. 集合の要素として出てくる値 : にランダムな整数を割り当てます。

2. 集合のハッシュは、その集合の各要素に割り当てられた整数の総 XOR です。

ABC250 E - Prefix Equality

集合の比較なら Zobrist hashing ですね!
先頭 項のハッシュを前計算しておけば、クエリ部分は 時間 / クエリ になります。

from random import *

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# ランダムな整数を割り当て
table = {}
for a in A:
    table[a] = randrange(1 << 60)
for b in B:
    table[b] = randrange(1 << 60)

# 先頭 i 項のハッシュを前計算
hashA = [0]
setA = set()
for a in A:
    if a in setA:
        hashA.append(hashA[-1])
    else:
        setA.add(a)
        hashA.append(hashA[-1] ^ table[a])

hashB = [0]
setB = set()
for b in B:
    if b in setB:
        hashB.append(hashB[-1])
    else:
        setB.add(b)
        hashB.append(hashB[-1] ^ table[b])

# クエリに答える
Q = int(input())
for i in range(Q):
    x, y = map(int, input().split())
    print("Yes" if hashA[x] == hashB[y] else "No")

https://atcoder.jp/contests/abc250/submissions/31642562

チェスの盤面をハッシュする

集合のハッシュができることは分かりましたが、チェスの盤面をハッシュするにはどうすればいいでしょうか?

チェスの盤面のイラスト ← チェスの盤面

チェスの盤面をうまく集合として表しさえすればいいですね。

そこで、(駒の種類, 駒の色, 駒の位置) を 要素にして、これらの集合でチェスの盤面を表してみましょう。駒の種類は 種類、駒の色は 種類、駒の位置は 種類あるので、 個のランダムな整数を割り当てれば、チェスの盤面をハッシュすることができます。

ある盤面のハッシュから次の盤面のハッシュを計算するには、動いた駒の動く前の位置での値を XOR して引き、動いた後の位置での値を XOR して足せば良いです。

このように、集合の つの要素だけが変化するような場合では、Zobrist hashing が役に立ちがちです。

モノグサプログラミングコンテスト2022(AtCoder Beginner Contest 238) G - Cubic?

立方数ではなく平方数である場合

を左から累積積を計算し、平方数で割れるだけ割ったものを とします。すなわち、素因数分解をしたあと、指数の累積和 をしたものです。
これが で一致していれば、その間の積 は平方数です。

しかし、累積積は非常に大きくなるので を直接計算することはできません。
そこで、Zobrist hashing を使ってみましょう。各素因数にランダムな整数を割り当てて、その素因数が入っていたら XOR という感じでハッシュを計算します。

これで、 時間で解くことができます。

立方数である場合

素因数分解をしたあと、指数の累積和 をしたものを とします。
この場合、各素因数にランダムな整数を割り当てて、その素因数が入っていたら XOR という方法は使えません。なぜなら、 個入っているからといって に割り当てられた整数を 回 XOR すると、元に戻ってしまうからです。

しかし、チェスの盤面のハッシュができるならこれもハッシュできるはずです。うまく集合として表しましょう。

(素因数, 指数) を 要素にして、これらの集合でチェスの盤面を表すのが良いですね。
つまり、 回掛かっている場合と 回掛かっている場合と 回掛かっている場合で別の乱数を用意するということです。
( 回掛かっている場合は集合に入れないものとすれば、 回掛かっている場合の乱数は要らなくなります。)

import sys
from random import randrange
input = sys.stdin.readline
MAX = 10 ** 6

N, Q = map(int, input().split())
A = list(map(int, input().split()))

# ランダムな整数を割り当てる
table = [[0] * (MAX + 1)] * 3
table[1] = [randrange(1 << 60) for _ in range(MAX + 1)]
table[2] = [randrange(1 << 60) for _ in range(MAX + 1)]

# 線形ふるい
primes = []
min_factor = [0] * (MAX + 1)
for i in range(2, MAX + 1):
    if min_factor[i] == 0:
        primes.append(i)
        min_factor[i] = i
    f = min_factor[i]
    for p in primes:
        j = i * p
        if p > f or j > MAX:
            break
        min_factor[j] = p

# ハッシュを計算
B = [0]
cnt = [0] * (MAX + 1) # 素数の出てきた回数
h = 0

def add(p: int): # 素数を追加
    global h
    h ^= table[cnt[p]][p]
    cnt[p] += 1
    if cnt[p] == 3:
        cnt[p] = 0
    h ^= table[cnt[p]][p]

for a in A:
    while a > 1:
        p = min_factor[a]
        add(p)
        a //= p
    B.append(h)

# クエリを処理
for _ in range(Q):
    L, R = map(int, input().split())
    print("Yes" if B[L - 1] == B[R] else "No")

https://atcoder.jp/contests/abc238/submissions/31642741

tatyam icon
この記事を書いた人
tatyam

競技プログラミングと音ゲーと素数大富豪をしています。 AtCoder銅冠 (https://atcoder.jp/users/tatyam) ICPC 2020 Asia Yokohama Regional 3 位 (good_yamikin) ICPC 2021 Asia Yokohama Regional 3 位 (tonosama)

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2021年4月18日
ベズー係数とN項の拡張ユークリッドの互除法
0214sh7 icon 0214sh7
2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2021年4月26日
CPCTF2021 作問者writeup by hukuda222
hukuda222 icon hukuda222
2021年4月25日
CPCTF2021 作問者writeup by xxpoxx
xxpoxx icon xxpoxx
2018年12月16日
ICPCアジア地区横浜大会参加記【アドベントカレンダー2018 52日目】
eiya icon eiya
2022年5月2日
CPCTF22 PPC 作問陣Writeup
ebi icon ebi
記事一覧 タグ一覧 Google アナリティクスについて