AtCoder ABC 313 D - Odd or Even (青色, 550 点)

みたいな連立方程式を解いた経験があれば、思いつきやすいかもしれない。

• 問題へのリンク

問題概要 (インタラクティブ)

0 と 1 のみからなるサイズ の数列 があるが、未知である。いくつか質問を繰り返すことで、この数列を特定したい。

最大で 回まで質問することができる。

各質問では、 個の要素のうち、ちょうど 個の要素の index を指定する。それに対して、それら 個の要素の XOR 和が返される。

数列 を特定せよ。

制約

• 
• は奇数

考えたこと：対称的な連立方程式

前提として、次のような連立方程式を解けるようにしておこう！

^ ^ = 1
^ ^ = 0
^ ^ = 1
^ ^ = 1

これを満たす 0-1 変数 の値を求めたい。こういう対称的な連立方程式は、すべて足す (今回は XOR の意味で) ものと相場は決まっている。

ここで、 ^ ^ = のように、奇数個の の XOR 和は になることに注意しよう。このことに注意して、上の式をすべて足すと

^ ^ ^ = 1

となる。再びこの式と、もとの式との XOR 和をとっていくことで、 が求められる。たとえば

( ^ ^ ^ ) ^ ( ^ ^ ) =

になることに注目しよう。このことを利用すると、

= 1 ^ 1 = 0

と求められる。同様に も求められる。なお、このような解法は前例がある。ぜひ、次の問題も解いてみよう！

drken1215.hatenablog.com

これを踏まえて

これを踏まえると、今回の問題も次のように解ける。たとえば、、 とする。

このとき、まず

• の XOR 和
• の XOR 和
• の XOR 和
• の XOR 和
• の XOR 和
• の XOR 和

を聞くことで、 の値を求めることができる。一般に、奇数 に対して、 の値を同様に求めることができる。

これができれば、残りは簡単だ。 の値が分かっているので、

• の XOR 和
• の XOR 和
• 
• の XOR 和

を聞くことで、 の値も特定できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N, -1);
    
    // 聞く
    auto ask = [&](const vector<int> &ids) -> int {
        cout << "?";
        for (auto id : ids) cout << " " << id+1;
        cout << endl;
        int res;
        cin >> res;
        return res;
    };
    
    // A[0], A[1], ..., A[K] を求める
    int sum = 0;
    vector<int> ans(N);
    for (int i = 0; i < K+1; ++i) {
        vector<int> ids;
        for (int j = 0; j < K+1; ++j) {
            if (j == i) continue;
            ids.push_back(j);
        }
        ans[i] = ask(ids);
        sum ^= ans[i];
    }
    for (int i = 0; i < K+1; ++i) A[i] = sum ^ ans[i];
     
    // A[K+1], A[K+2], ..., A[N-1] を求める
    for (int i = K+1; i < N; ++i) {
        vector<int> ids({i});
        int sub = 0;
        for (int j = 0; j < K-1; ++j) {
            sub ^= A[j];
            ids.push_back(j);
        }
        ans[i] = ask(ids);
        A[i] = sub ^ ans[i];
    }
    
    cout << "!";
    for (int i = 0; i < N; ++i) cout << " " << A[i];
    cout << endl;
}

別解

要素を乱択するのを繰り返した上で、Gauss-Jordan の掃き出し法を用いることで、大体の場合解ける。