AtCoder が提供しているABC（AtCoder Beginner Contest）367 F問題をC++とPythonで解いてみました。ABC367は、2024年8月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Rearrange Query（Difficulty : 1540）
問題の詳細は、リンク先をご覧ください。
変換した値の累積和を求めます。AtCoder Problems による Difficulty は 1540 でした。
解答案
制約 $1 \leqq N, Q \leqq 2 \times 10^5$ であるため、$O(NQ)$ となる処理は間に合いません（それぞれの数字の頻度の累積和を求めて、集合にある個数を求めるなど）。
部分集合が一致していれば、部分集合の和は一致しています。逆に部分集合の和が一致していても、部分集合が一致しているとは言えません。ここで [1, N] を [0, 264) にランダムにマッピングして和を求めれば、部分集合の和が一致しない多くの場合、部分集合も一致しなくなります。
1からNに対応する乱数を割り当てて、累積和を求めて、部分集合の和が一致するか確かめます。
C++ プログラム例（ABC367F）
[1, N] を [0, 264) に変換するために、線形合同法を使いました。英語版のWikipediaの記事を参考に、法が $2^{64}$ となる Knuth の式を採用しました。
- $x_{n+1} = 6364136223846793005 x_n + 1442695040888963407$
- $2^{64}$ を法として計算する。これは、unsigned long long で計算すれば、自然と実現できます。
- 初期値は、大きな素数（1999000021）とした。
次に変換した値の累積和を求めて、2つの区間の和が一致しているか確かめます。このプログラムでは、部分集合の要素の数は確認していません（公式解説で紹介されているプログラムも同様でした）。
以下が、C++プログラムです。AC（Accepted＝正しいプログラム）と判定されました。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> b(n);
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
vector<ull> h(n + 1);
h[0] = 1999000021;
for (int i = 0; i < n; ++i) {
h[i + 1] = h[i] * 6364136223846793005ULL + 1442695040888963407ULL;
}
vector<ull> sum_a(n + 1, 0);
vector<ull> sum_b(n + 1, 0);
for (int i = 0; i < n; ++i) {
sum_a[i + 1] = sum_a[i] + h[a[i]];
sum_b[i + 1] = sum_b[i] + h[b[i]];
}
for (int i = 0; i < q; ++i) {
int La, Ra, Lb, Rb;
cin >> La >> Ra >> Lb >> Rb;
--La;
--Lb;
if (sum_a[Ra] - sum_a[La] == sum_b[Rb] - sum_b[Lb]) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}もう少し小さい範囲へのマッピングも試してみます。以下の $2^{32}$ を法とする以下の線形合同法を採用しました。
- $x_{n+1} = 1664525 x_n + 1013904223$
- $2^{32}$ を法として計算する。これは、unsigned int で計算すれば、自然と実現できます。
- 初期値は、1 とした。
このプログラムでも AC と判定されました。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
int main()
{
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> b(n);
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
vector<uint> h(n + 1);
h[0] = 1;
for (int i = 0; i < n; ++i) {
h[i + 1] = h[i] * 1664525U + 1013904223U;
}
vector<uint> sum_a(n + 1, 0);
vector<uint> sum_b(n + 1, 0);
for (int i = 0; i < n; ++i) {
sum_a[i + 1] = sum_a[i] + h[a[i]];
sum_b[i + 1] = sum_b[i] + h[b[i]];
}
for (int i = 0; i < q; ++i) {
int La, Ra, Lb, Rb;
cin >> La >> Ra >> Lb >> Rb;
--La;
--Lb;
if (sum_a[Ra] - sum_a[La] == sum_b[Rb] - sum_b[Lb]) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}Python プログラム例（ABC367F）
Python版も基本的な考え方は同じです。32ビット合同線形法のプログラムを移植しました。以下となります。
"""AtCoder Beginner Contest 367 F"""
MOD = 2 ** 32
n, q = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
h = [0] * (n + 1)
h[0] = 1
for i in range(n):
h[i + 1] = (h[i] * 1664525 + 1013904223) % MOD
sum_a = [0] * (n + 1)
sum_b = [0] * (n + 1)
for i in range(n):
sum_a[i + 1] = (sum_a[i] + h[a[i]]) % MOD
sum_b[i + 1] = (sum_b[i] + h[b[i]]) % MOD
for i in range(q):
La, Ra, Lb, Rb = map(int, input().split())
La -= 1
Lb -= 1
diff_a = (sum_a[Ra] - sum_a[La] + MOD) % MOD
diff_b = (sum_b[Rb] - sum_b[Lb] + MOD) % MOD
print("Yes" if diff_a == diff_b else "No")こちらも「AC」と判定されました。
最後に
大きな値の剰余を計算して値が同じであれば、同一視するという意味で、ABC339F問題（解説記事）が類題となります。
引き続き ABC の問題を紹介していきます。
