Two Prisoners and 01 Array

解説

以下では、列の添字を $0$ から数えます。つまり $B = (B_0, B_1, \ldots, B_{2^N - 1})$ とします。

方針

$01$ 列 $C$ に対して、 $C_i = 1$ である添字 $i$ すべての排他的論理和（XOR）を $f(C)$ と書きます。 $1$ が $1$ つもなければ $f(C) = 0$ です。

Alice と Bob は「 $f(B') = X$ となる $B'$ を伝える」と決めておきます。

Alice の操作

$B$ の $p$ 番目を反転した列を $B'$ とします。 $B_p$ が $0$ から $1$ に変わるときは添字 $p$ が新たに加わり、 $1$ から $0$ に変わるときは添字 $p$ が取り除かれます。 XOR では加えることと取り除くことが同じ操作なので、どちらの場合も

$$f(B') = f(B) \oplus p$$

が成り立ちます。

したがって $p = f(B) \oplus X$ と選べば、 $f(B') = f(B) \oplus f(B) \oplus X = X$ となります。 $f(B)$ と $X$ はどちらも $0$ 以上 $2^N - 1$ 以下なので、 $p$ も $0$ 以上 $2^N - 1$ 以下であり、必ず列の中の添字になります。

反転するのは $1$ か所だけなので、 $B'$ と $B$ のハミング距離は $1$ です。

なお $f(B) = X$ のときは $p = 0$ です。添字 $0$ は $f$ の値に影響しないため、 $0$ 番目を反転しても、何も変えずに $B' = B$ としても構いません。

Bob の操作

受け取った $B'$ から $f(B')$ を計算して出力します。上で示したとおり、これは $X$ に一致します。

列の長さが $2^N$ であることについて

Alice が作れる $B'$ は、 $B$ 自身と $1$ か所を反転した列の、合わせて $2^N + 1$ 通りです。一方で伝えたい $X$ は $2^N$ 通りあります。添字が $0$ から $2^N - 1$ までちょうど $N$ ビットで表せるため、 $1$ か所の反転で $f$ の値を任意の値に変えられます。

実装

$1$ 行目の文字列が Alice か Bob かで処理を分けます。問題文の添字は $1$ から始まるので、 $i$ 番目の要素を添字 $i - 1$ として扱う点に注意してください。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#include <bits/stdc++.h>
using namespace std;

int main() {
    string role;
    int T;
    cin >> role >> T;
    while (T--) {
        int n;
        cin >> n;
        int x = 0;
        if (role == "Alice") cin >> x;
        vector<int> b(1 << n);
        int s = 0;
        for (int i = 0; i < (1 << n); i++) {
            cin >> b[i];
            if (b[i]) s ^= i;
        }
        if (role == "Alice") {
            b[s ^ x] ^= 1;
            for (int i = 0; i < (1 << n); i++) cout << b[i] << " \n"[i + 1 == (1 << n)];
        } else {
            cout << s << "\n";
        }
    }
}

計算量

各テストケースについて、どちらの実行でも $O(2^N)$ 時間です。