AtCoder が提供しているABC（AtCoder Beginner Contest）337 のE問題をC++とPythonで解いてみました。ABC337は、2024年1月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Bad Juice（Difficulty : 1155）
問題はリンク先をご覧ください。
ジュースの番号を2進数と考えて、友人はそれぞれの桁を担当します。AtCoder Problems による Difficulty は 1155 でした。
解答案
仮に友人が3名いたとします。この場合、腹を壊す友人の組み合わせは、23=8 通りあります。番号1から8のジュースを2進数の0から7に紐づければ、3名の友人で番号1から8までのどのジュースが腐っているか分かります。
C++ プログラム例（ABC337E）
n-1 が、2進数で n_bit になったとします（8ー13行目）。友人の数は n_bit 人（2進数 n_bit 桁）となります。
番号0から番号n-1を2進数と考えた場合に、友人iには、下i桁のビットがセットされているジュースを割り当てます。内部的には、0からn-1として、インタラクティブな問い合わせは、1からnとして取り扱っています。
- 問い合わせる場合は、ジュースの番号に1を加えます（20行目）。
- 復元したジュースの番号に1を加えた値を出力します（38行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int n_bit = 0;
for (int i = 0; i < 10; ++i) {
if (((n - 1) & (1 << i)) != 0) {
n_bit = i + 1;
}
}
cout << n_bit << endl;
for (int i = 0; i < n_bit; ++i) {
vector<int> juice;
for (int j = 0; j < n; ++j) {
if ((j & (1 << i)) != 0) {
juice.push_back(j + 1);
}
}
cout << juice.size();
for (int j = 0; j < juice.size(); ++j) {
cout << " " << juice[j];
}
cout << endl;
}
string s;
cin >> s;
int result = 0;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '1') {
result += (1 << i);
}
}
++result;
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC337E）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 337 E"""
n = int(input())
for i in range(10):
if (n - 1) & (1 << i) != 0:
n_bit = i + 1
print(n_bit)
for i in range(n_bit):
juice = []
for j in range(n):
if j & (1 << i) != 0:
juice.append(j + 1)
print(len(juice), end=" ")
print(*juice)
s = input()
result = 0
for i, ch in enumerate(s):
if ch == '1':
result = result + (1 << i)
result += 1
print(result)こちらも「AC」と判定されました。
最後に
インタラクティブな問題は、色ひとつ難しくなる印象です。この問題自体は、数学的なパズルとしてよく紹介されます。
引き続き ABC の問題を紹介していきます。
