AtCoder が提供しているABC（AtCoder Beginner Contest）347 のD問題をC++とPythonで解いてみました。ABC347は、2024年3月30日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Ideal Holidays（Difficulty : 1041）
問題はリンク先をご覧ください。
XとYについて、必ず1としなければならないビット位置を特定します。AtCoder Problems による Difficulty は 1041 でした。
解答案
入力例1について考察します。
$X$ の立っているビット数が3個、$Y$の立っているビット数が4個、$X \oplus Y= 7$ となる $X$ と $Y$ を求めます。
7の二進数表記：0 0 0 0 0 1 1 1
ビットが設定されている3桁について $X$ から1桁、$Y$ から2桁選びます。残りの2桁は同じ桁のビットを設定すれば $1 \oplus 1 = 0$ となり、条件を満たします。
X：0 0 0 1 1 0 0 1
Y：0 0 0 1 1 1 1 0
$A$ と $B$ は違う振り分けもできます。
X：0 0 0 1 1 0 1 0
Y：0 0 0 1 1 1 0 1
共通で設定するビット位置は60桁以内の好きな桁を選ぶことができます。例えば以下です。
X：1 1 0 0 0 0 1 0
Y：1 1 0 0 0 1 0 1
解が存在しない条件
$X$ と $Y$ が存在しない条件として以下があります。ここで $C$ の立っているビット数を pc（popcount of c）とします。
- $A + B < pc$
popcount of C が $A+B$ よりも多い場合は、$X$ と $Y$ は存在しません。 - $(60\; -\; pc) \times 2 + pc < A + B$
左辺は、$X$ と $Y$ で1を設定できる上限の個数となります。これが $A+B$ より小さい場合は、$X$ と $Y$ は存在しません。 - $A \geqq B$ と仮定します。
$A\; -\; B > pc$ であると、$X$ の $pc$ 個を1に設定しても、それ以外に $X$ だけに1を設定しなければならない桁が存在します。 - $(A + B\; -\; pc) \bmod 2 \neq 0$
この場合は、$X$ か $Y$ のどちらかだけ余分に設定されるビットが発生します。
逆にこの条件を満たさない場合は、$A$ と $B$ で多い方からビットを設定していけば、$X \oplus Y= C$ となる $X$ と $Y$ を求めることができます。
C++ プログラム例（ABC347D）
プログラムの補足です。
- $C$ でビットが立っている位置を set コンテナ bits_c、その個数を p_c として求めます（11ー18行目）。
- 上記で考察した $X$ と $Y$ が存在しない条件を満たす場合は、-1 を出力して、プログラムを終了します（19ー26行目）。
- $X$ と $Y$ について、最下位ビットから以下の処理をします。
- bits_c に含まれている場合は、$A$ と $B$ で大きい方からビットを設定します。残り設定できるビットを used_x、used_y として記憶しておきます（36ー42行目）。
- bits_c に含まれていない場合は、$X$ と $Y$ の共通で設定するビット数に余分があれば、それぞれ設定します（44ー48行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
ull a, b, c;
cin >> a >> b >> c;
ull p_c = 0;
set<int> bits_c;
for (int i = 0; i < 62; ++i) {
if ((c & (1ULL << i)) != 0) {
++p_c;
bits_c.insert(i);
}
}
if ((p_c > a + b)||((60 - p_c) * 2 + p_c < a + b)) {
cout << -1 << endl;
return 0;
}
if ((max(a, b) - min(a, b) > p_c)||((a + b - p_c)% 2 != 0)) {
cout << -1 << endl;
return 0;
}
ull x = 0;
ull y = 0;
ull used_x = a;
ull used_y = b;
int common_used = 0;
int common_limit = (a + b - p_c) / 2;
for (ull i = 0; i < 62; ++i) {
if (bits_c.find(i) != bits_c.end()) {
if (used_x >= used_y) {
x |= (1ULL << i);
--used_x;
} else {
y |= (1ULL << i);
--used_y;
}
} else {
++common_used;
if (common_used <= common_limit) {
x |= (1ULL << i);
y |= (1ULL << i);
}
}
}
cout << x << " " << y << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC347D）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 347 D"""
import sys
a, b, c = map(int, input().split())
p_c = 0
bits_c = set()
for i in range(62):
if (c & (1 << i)) != 0:
p_c += 1
bits_c.add(i)
if p_c > a + b or (60 - p_c) * 2 + p_c < a + b:
print(-1)
sys.exit()
if max(a, b) - min(a, b) > p_c or (a + b - p_c) % 2 != 0:
print(-1)
sys.exit()
x = 0
y = 0
used_x = a
used_y = b
common_used = 0
common_limit = (a + b - p_c) // 2
for i in range(62):
if i in bits_c:
if used_x >= used_y:
x |= (1 << i)
used_x -= 1
else:
y |= (1 << i)
used_y -= 1
else:
common_used += 1
if common_used <= common_limit:
x |= (1 << i)
y |= (1 << i)
print(x, y)こちらも「AC」と判定されました。
最後に
この問題は、コンテスト中にほぼ解けていました。ただし、ビット位置の格納に vector コンテナを使っていました。結果的に配列外参照していて、RE（Runtime Error）がでていて、これが取り切れず、時間切れとなりました。残念でした。
記事では、set コンテナを使ったプログラムを紹介しました。
引き続き ABC の問題を紹介していきます。
