D - Odd or Even Editorial by Nyaan
まず \(N = K + 1\) の時の解法を説明します。以下では \(s_i\) はクエリに対するジャッジの解答とします。
\(i\) 回目のクエリでは \((i, i+1, \dots, i+K-1)\) をクエリで投げます (値が \(N\) 以上になったらその都度 \(N\) を引く) 例えば \(N=4,K=3\) では以下のようなクエリを投げます。
\[ \begin{aligned} A_1 + A_2 + A_3 &= s_1\\ A_2 + A_3 + A_4 &= s_2\\ A_3 + A_4 + A_1 &= s_3\\ A_4 + A_1 + A_2 &= s_4\\ \end{aligned} \]
\(N\) 回のクエリにおいて \(A_1, A_2, \dots, A_N\) は左辺に \(K\) 回登場します。ここで \(K\) は奇数なので、\(A_1 + A_2 + \dots +A_N\) の偶奇は \(s_1 + s_2 + \dots + s_N\) の偶奇と一致します。よって、両辺の総和を取ることで \(A_1 + A_2 + \dots + A_N\) の偶奇を決定できます。
ここから適切に差を取ることで \(A_1, A_2, \dots, A_N\) の偶奇を 1 個ずつ全て決定できます。たとえば \(N=4, K=3\) の場合、
\[A_4 = (A_1 + A_2 + A_3 + A_4) - (A_1 + A_2 + A_3)\]
なので \(A_4\) の偶奇は \(A_1 + A_2 + A_3 + A_4\) の偶奇と \(s_1\) から決定できます。(\(A_1, A_2, A_3\) も同様です) 以上より \(N=K+1\) の場合は解くことができました。
実はこの解法をそのまま応用すると\(N\) が一般の場合でも解くことができます。はじめに \(N=K+1\) の場合と同様に \(K+1\) 回かけて \(A_1, A_2, \dots, A_{K+1}\) を特定します。その後、\(i = K+2, K+3, \dots, N\) について、\(i\) 回目のクエリでは \((1, 2, \dots, K-1, i)\) を投げます。すると、
\[ \begin{aligned} A_i = s_i - (A_1 + A_2 + \dots + A_{K-1}) \end{aligned} \]
なので \(A_i\) の偶奇が \(A_1, A_2, \dots, A_{K-1}, s_i\) から決定できます。これを繰り返すことで \(A\) の全ての要素を特定できます。
以上よりこの問題を \(N\) 回のクエリで解くことができました。
- 実装例(C++)
#include <bits/stdc++.h>
using namespace std;
void out(vector<int> v) {
for (unsigned i = 0; i < v.size(); i++) {
cout << v[i] << " \n"[i + 1 == v.size()];
}
}
int main() {
int N, K;
cin >> N >> K;
auto send = [&](vector<int> v) {
for (auto& x : v) x++;
cout << "? ", out(v);
cout.flush();
int x;
cin >> x;
return x;
};
vector<int> ans(N);
{
int r = 0;
for (int i = 0; i < K + 1; i++) {
vector<int> v;
for (int j = 0; j < K + 1; j++)
if (i != j) v.push_back(j);
ans[i] = send(v);
r ^= ans[i];
}
for (int i = 0; i < K + 1; i++) ans[i] ^= r;
}
{
vector<int> v(K);
int s = 0;
for (int i = 0; i < K - 1; i++) v[i] = i, s ^= ans[i];
for (int i = K + 1; i < N; i++) {
v.back() = i;
int t = send(v);
ans[i] = s ^ t;
}
}
cout << "! ", out(ans);
cout.flush();
}
posted:
last update: