とても色んな解法が考えられる問題ですね。ハッシュで殴るのが最も簡単だとは思います。そのほかにもさまざまな解法が考えられます。
問題概要
2 つのサイズ の整数列
と
が与えられます。
これらの数列に対して 回のクエリが与えられます。各クエリでは
以下の整数
が与えられますので、
- 数列
の先頭から
個の要素：
- 数列
の先頭から
個の要素：
が集合として一致するかどうかを判定してください。
制約
解法 1：ハッシュで殴る
この問題の難しさは
- 各
に対して、各数列の先頭から
個とってできる集合を求めたいが、それらすべて保存するのはメモリが足りない
- 各クエリに対して、集合が一致するかどうかを判定するには
の時間を要する (
std::setの場合は)
というところにあります。しかしこれらの問題を一度にまとめて解決してしまう方法があります。それは Zobrist Hash などのハッシュを使う方法です。
各 に対して、
からなる集合を 1 つの整数値として表現してしまうのです。
そのようなことが可能なハッシュであればなんでもよいのですが、集合をハッシュ値で表すには Zobrist Hash が便利です。その方法はいたって簡単です！
- 集合の各要素に対して乱数を割り当てる
- 割り当てた乱数の XOR をとる
乱数を割り当てる部分は、いい感じの関数があります。Codeforces ブログで提供されているので、これをパクらせてもらいましょう！！！
実行してみないと値が分からない chrono::steady_clock::now().time_since_epoch().count() を活用しているため、とても強いです。
総合して、計算量は です。
Zobrist Hash についての remark
- Zobrist Hash は XOR をとるものであるため、要素の「挿入」と「削除」がともに高速にできます
- Zobrist Hash は「要素の種類」のみに対応しているため、「要素の個数」まで知りたい場合は、XOR をとる代わりに「普通の和」をとります (参考：chokudai さんのツイート)
#include <bits/stdc++.h> using namespace std; // 整数値 x にハッシュ値を割り当てる関数 struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator() (uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } } rng; int main() { // Zobrist Hash // hashA[i] := 数列 a の先頭から i 個分の集合を表すハッシュ値 int N; cin >> N; // N 個の入力を受け取って、Zobrist Hash を返す関数 auto hashing = [&]() -> vector<uint64_t> { vector<uint64_t> hash(N + 1, 0); set<long long> S; // すでにあるかを確認する for (int i = 0; i < N; ++i) { long long x; cin >> x; // すでに含まれている場合は何もしない if (S.count(x)) { hash[i + 1] = hash[i]; continue; } S.insert(x); hash[i + 1] = hash[i] ^ rng(x); } return hash; }; const auto& hashA = hashing(); const auto& hashB = hashing(); // クエリ処理 int Q; cin >> Q; while (Q--) { int x, y; cin >> x >> y; if (hashA[x] == hashB[y]) cout << "Yes" << endl; else cout << "No" << endl; } }
解法 2：set で頑張る
明快な解説が kyopro_frineds さんによってなされています！
解法 3：数列 a を正規化して、種類数と最大値
とても頭の良い解法です。適切な数値変換により、数列 は
というように、「新しく登場する値は、今まで登場した値の最大値 + 1」という状態に変形することが可能です。
このように変形した状態ならば、A と B の集合一致性を「種類数と最大値の一致」のみで判定可能になります。
