AtCoder が提供しているABC（AtCoder Beginner Contest）313 のD問題をC++とPythonで解いてみました。ABC313は、2023年8月5日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Odd or Even（Difficulty : 1630）
問題はリンク先をご覧ください。
XOR 演算を使うインタラクティブな問題でした。AtCoder Problems による Difficulty は 1630 でした。
解答案
K が奇数であるため、数列 A の最初の K+1 個を K+1 回の質問で決定することができます。入力例である A = (1, 0, 1, 1, 0) 、N=5、K=3 の場合の手順を説明します。
最初の4（3+1）個について以下の質問をします。ここでは、排他的論理和 XOR を ‘+’ で表現します。Ai ＋Ai =0、1 + 1 = 0 となります。
- A2 + A3 + A4 = 0 (0 + 1 + 1) ※A1以外の排他的論理和
- A1 + A3 + A4 = 1 (1 + 1 + 1) ※A2以外の排他的論理和
- A1 + A2 + A4 = 0 (1 + 0 + 1) ※A3以外の排他的論理和
- A1 + A2 + A3 = 0 (1 + 0 + 1) ※A4以外の排他的論理和
上記式の左辺と右辺をそれぞれ加えると以下となります。これは Ai がそれぞれ3回（K回）表れるため演算の結果では Ai がひとつになるためです。
S = A1 + A2 + A3 + A4 = 1 (0 + 1 + 0 + 0)
このため、A1 から A4 の値は、以下となります（実際に一致しています）。
- A1 = S + A2 + A3 + A4 = 1 (1 + 0)
- A2 = S + A1 + A3 + A4 = 0 (1 + 1)
- A3 = S + A1 + A2 + A4 = 1 (1 + 0)
- A4 = S + A1 + A2 + A3 = 1 (1 + 0)
残りの A5 は、例えば質問 A1 ＋A2 ＋A5 ＝ 1 の応答と A1 と A2 の値が分かっているため、A5 = (A1 ＋A2 ＋A5) + A1 + A2 = 0 と計算ができます。
一般的に同じ手順で、A の全ての要素を求めることができます。
- 数列 A の最初の K+1 個について、上記のように K+1 個の質問で値が分かります。
- 残りの Nー(K+1) 個を、分かっていない値を1個だけ含めた質問により、その値が計算できます。
C++ プログラム例（ABC313D）
上記の手順をプログラムとして表現しました。
- K+1 個の質問をして、その応答の和 sum を求めます（12ー22行目）。
- 和 sum から、最初の K+1 個の値を求めます（23ー25行目）。
- 1、2、K-1、残りの要素を組にした質問とその応答から（28ー33行目）、残りの要素の値を計算します（34ー36行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<unsigned int> result(n + 1, 0);
unsigned int sum = 0;
vector<unsigned int> temp(k + 2, 0);
for (int i = 1; i <= k + 1; ++i) {
cout << "? ";
for (int j = 1; j <= k + 1; ++j) {
if (i != j) {
cout << j << " ";
}
}
cout << endl;
cin >> temp[i];
sum ^= temp[i];
}
for (int i = 1; i <= k + 1; ++i) {
result[i] = sum ^ temp[i];
}
for (int i = k + 2; i <= n; ++i) {
cout << "? ";
for (int j = 1; j < k; ++j) {
cout << j << " ";
}
cout << i << endl;
cin >> result[i];
for (int j = 1; j < k; ++j) {
result[i] ^= result[j];
}
}
cout << "! ";
for (int i = 1; i <= n; ++i) {
cout << result[i] << " ";
}
cout << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC313D）
C++ のプログラムを移植しました。変数名 sum は、Python の組込み関数と名前が重複しているため、変数名を s に変更しました。また、C++ 版と異なり、質問と解答はリスト print_data に格納して、print でまとめて出力しています（12、23行目）。
"""AtCoder Beginner Contest 313 D"""
n, k = map(int, input().split())
result = [0] * (n + 1)
s = 0
temp = [0] * (k + 2)
for i in range(1, k + 2):
print_data = []
for j in range(1, k + 2):
if i != j:
print_data.append(j)
print("?", *print_data)
temp[i] = int(input())
s ^= temp[i]
for i in range(1, k + 2):
result[i] = s ^ temp[i]
for i in range(k + 2, n + 1):
print_data = []
for j in range(1, k):
print_data.append(j)
print_data.append(i)
print("?", *print_data)
result[i] = int(input())
for j in range(1, k):
result[i] ^= result[j]
print("!", *result[1:])こちらも「AC」と判定されました。
最後に
この問題はコンテスト中には解けませんでした。公式解説が理解できたため紹介しました。結果的に難易度:青問題の初めての解説となりました。
インタラクティブな問題はテストが難しいです。入出力例の N=5、K=3 の場合と A の最後の要素を抜いた N=4、K=3 の場合に、サーバ応答を手で入力してテストしました。
引き続き ABC の問題を紹介していきます。
