ハッシュ
- ある状態や数列を一意なハッシュ値に変換することで上手く判定や数え上げをやる
- ハッシュ化する手法は「unodered_mapやset」「ローリングハッシュ」「Zobrist Hash」
- ローリングハッシュは数列をハッシュ値にするのが得意(衝突しやすい)
- 衝突させないために複数ハッシュで、チャレンジ対策にランダム素数で自分は使ってる
- keymoonさんのこういう話もある
- 2Dローリングハッシュというのがあるみたい
- 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
問題
ローリングハッシュ
- yukicoder No.430 文字列検索
- CF434 Polycarp's phone book 解説
- yukicoder No.599 回文かい 解説
- CF451 Restoring the Expression 解説
- yukicoder No.765 ukuku 2 解説
- AOJ Where's Wally (2Dローリングハッシュ)
Zobrist
- CodeChef Nasty Queries
- CF439 The Untended Antiquity
- CSA62 Trees Partition
- HackerRank Sorting Lists (難)
- HE Shubham and Subarrays
- HR "✝" 解説
その他
- CC Chef and Isomorphic Array （平方分割も使うのでむずい）
【覚書】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するだけで良くなる。
そのため、状態のような各要素のパリティだけ持っておきたい場合のハッシュ化を効率よく行える。
