コンテスト中AC:A〜D
Eはコンテスト後に解説を読み、自分がコンテスト中に考えていた発想で問題なさそうだったので、その方針でなんとかACできました。
E問題について書いたので、記事のタイトルはEをメインにしました。
E - Prefix Equality
自分の実装
こちらの解説と多分同じ考え方だと思います。(多分)
方針
大雑把なイメージです。
から得られる集合を
とします。同様に、
から得られる集合を
とします。
と等しい
が存在すると仮定し、その中で最小の
を
とします。
と増加させ、
を追加していくと、そのうち集合として等しくなくなります(但し、便宜上
に
に含まれない値があるものとします。)。この時の
を
とします。
この時、に対しては、
を満たす
が全て等しくなります。
よって、各について、
の区間を前計算しておけば、各クエリに
で答えられます。
前計算の計算量
愚直に各について、
の区間を求めようとすると、少なくとも
くらいにはなってしまいます。
しかし、実はと探索していくと、
の探索範囲も増加するだけになり、結果として
くらいになります。
具体例と共になぜそうなるか書いていきたいと思います。
前計算の処理
以下の数列を例にします。
(-1は番兵)
以下の集合を定義します。
:
に含まれ、
ではまだ見つかっていない値の集合
:
と
に共通して存在する値の集合
について、
の先頭
項と
の先頭
項が等しくなるような
の区間を求めます。
初めとしておきます。
(1) に
を追加し、これに対応する
の区間を求めます。
であり、
に一致する値がないので、これに一致する
の区間は存在しません。
(2) に
を追加します。
です。
なので、
から
を削除して、
に追加します。
も同様です。
ここで、が空になりました。これは、
となったことを指します。よって、
のときに集合が等しくなる時の下限は
です。
下限が見つかったため、上限を調べます。
現在、です。
は
に含まれるので、
となります。
次のは
に含まれないので、この時点で、
となります。従って、半開区間
が
の時に集合として等しくなる
の区間です。
(3) は
に含まれ、更に
が空です。よって、
は一個前の
と等しく、かつ、
には
の区間が存在していることがわかります。
この場合、であることから、
についての
の区間は
の時と同じになります。
(4) を
に追加します。この時、新たに
の区間を再探索しますが、
からの探索として良いです。
なぜなら、は
に含まれるため、
を集合として等しくするために必要になるからです。また、
は
に含まれない最初の値なので、ここから探索を開始する必要があります。
の区間の探索をしますが、
で、これは
に含まれません。よって、
と等しい
の区間は存在しません。
(5) は
に存在するので、既に
の両方に共通して存在しています。そのため、
には追加しません。
の区間の探索をしますが、
で、これは
に含まれません。よって、
と等しい
の区間は存在しません。
(6) を
に追加し、
となります。
の区間を探索すると、
と進めると、両方
に含まれるので、
から削除し、
に追加します。
の時点で
が空になったので、
が、
と等しくなる下限です。
上限ですが、番兵として入れてあるが
に含まれないので、
の時は、
が該当の区間になります。
以上で、全てのに対する
の区間が求まりました。
例で示したように、は常に、
の
項目までに含まれない最初の値を指すようにしておきます。
すると、目項までと等しい区間を探す際に
から開始すればよくなります。
なぜなら、と等しい区間を探す際に、
は
を部分集合として含むため、少なくとも
と共通な値のみを含む
が必要となるからです。
これで、は増加させるだけでよいことがわかりました。
Zobrist Hash
公式解説にあったので解いてみました。
整数を乱数に変換します。これを
とします。
集合のハッシュ値を
と定義します。
また、数列の
項目までからなる集合から計算されるハッシュ値をそれぞれ
とします。
するとi番目のクエリは、
ならyes、そうでなければNo
と判定できます。
の計算方法については、累積的にXOR和をとっていけばよいのですが、一点注意が必要で、同じ値を2回以上XORを取らないようにします。(偶数回とると、0になるため)
Bonusの問題は、単純に区間のXORをとっても上記の問題を解決できないので、わかりませんでした。
ハッシュの衝突に関してはyoutubeの公式解説では、64bit整数ならくらいになるそうです。
なお、実装では 、 http://vivi.dyndns.org/tech/cpp/random.html
↑を参考に64bitのメルセンヌ・ツイスタに乱数をseed値として与えて生成しました。