Official

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: