AtCoder

ABC347 D問題(Popcount and XOR)を解く

AtCoder_ABC347_D

AtCoder が提供しているABC(AtCoder Beginner Contest)347 のD問題をC++とPythonで解いてみました。ABC347は、2024年3月30日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Ideal Holidays(Difficulty : 1041)

問題はリンク先をご覧ください。

ABC347 D問題 Popcount and XOR

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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA