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

hamayanhamayan's blog

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

ハッシュ

  • ある状態や数列を一意なハッシュ値に変換することで上手く判定や数え上げをやる
  • ハッシュ化する手法は「unodered_mapやset」「ローリングハッシュ」「Zobrist Hash」
  • ローリングハッシュは数列をハッシュ値にするのが得意(衝突しやすい)
  • Zobrist Hashは状態をハッシュ値にするのが得意(2^N通りあるような部分集合的な表現が得意)
  • 累積和とか複数の適当なハッシュを使うことで色々分かったりするらしい tomerunさんのブログのCLONEME

問題

ローリングハッシュ

Zobrist

【覚書】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するだけで良くなる。
そのため、状態のような各要素のパリティだけ持っておきたい場合のハッシュ化を効率よく行える。