はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるハッシュ問題まとめ

ハッシュ

  • ある状態や数列を一意なハッシュ値に変換することで上手く判定や数え上げをやる
  • ハッシュ化する手法は「unodered_mapやset」「ローリングハッシュ」「Zobrist Hash」
  • ローリングハッシュは数列をハッシュ値にするのが得意(衝突しやすい)
  • Zobrist Hashは状態をハッシュ値にするのが得意(2^N通りあるような部分集合的な表現が得意)
  • 累積和とか複数の適当なハッシュを使うことで色々分かったりするらしい tomerunさんのブログのCLONEME
  • 上手くハッシュを作ることで加算に対応させることもできる。「mod素数,r=10」を違う素数で幾つか用意して比較。この問題
  • multisetのハッシュ
    • multiset A = {a1, a2, ... , an}をハッシュ化する
    • この解説で登場 (setter,tester解はchokudaiさんの方法で、editorialist解はrngさんの方法)
    • chokudaiさんの方法
      • Zobrist Hashとほぼ同じなのだが、xorではなく和を使うと個数に対応したハッシュが作れる
    • rngさんの方法
      • aiが[0,MOD)の範囲にあるとき、rを[0,MOD)のランダムな数とすると(r+a1)(r+a2)...(r+an)がハッシュ値。衝突確率は多くてもn/MOD

【覚書】Zobrist Hashのやり方

Zobrist Hashが得意とするのが、状態のハッシュ化。

1. 各要素について乱数を割り当てる(long longくらいとっておくと安心)
2. 状態は含まれる要素の乱数を全てxorする

それだけ。
例えば、A=10, B=00, C=01だと
状態ABは10^00=10
状態ACは10^01=11
状態ABCは10^00^01=11
と表現できる。ある状態から要素を入れたり抜いたりする場合は、その要素の乱数をxorするだけで良くなる。
そのため、状態のような各要素のパリティだけ持っておきたい場合のハッシュ化を効率よく行える。