AtCoder

ABC269 C問題(Submask)を解く

AtCoder_ABC269_C

AtCoder が提供しているABC(AtCoder Beginner Contest)269 のC問題をC++とPythonで解いてみました。ABC269は、2022年9月17日21:00に実施されました。

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

C問題 Submask(Difficulty : 384)

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

ABC269 C問題 Submask

問題から読み取りにくいかもしれませんが、bit全検索を使う典型問題です。AtCoder Problems による Difficulty は、384 でした。ABC C問題としては標準的な難易度です。

解答案

問題を解く方針を書きだします。

  • 自然数 N を標準入力から読み取る。
  • N を2進数で表現したときに、1が立っている場所を調べる。
  • N の1が立っているそれぞれの場所で、0 または、1 を代入して条件を満たす数字を求めて保存する。
  • 保存した数字をすべて出力する。

大きな数字を使うため、型に注意が必要です。

C++ プログラム例(ABC269C)

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;

int main()
{
	ull n;
	cin >> n;

	vector<ull> p;
	vector<ull> result;

	for (ull i = 0; i < 64; ++i) {
		if ((n & (1ULL << i)) != 0) {
			p.push_back(i);
		}
	}

	for (ull bit = 0; bit < (1ULL << p.size()); ++bit) {
		ull n = 0;
		for (ull i = 0; i < p.size(); ++i) {
			if ((bit & (1ULL << i)) != 0) {
				n += (1ULL << p[i]);
			}
		}
		result.push_back(n);
	}

	for (int i = 0; i < result.size(); ++i) {
		cout << result[i] << endl;
	}

	return 0;
}

bit全検索を使う典型問題です。bit全検索については、Project Euler の問題18で解説しました。すべての 2N 通りについて、それぞれ 0 から 2N-1 を対応させて調べることをbit全検索と呼びます。

変数 N の1が立っている場所を vector コンテナ p に格納していきます。問題文から、p に格納される数は、15個以下となります。最大でも 0 から 215-1 までの数に対して、N の立っている位置の数を加えるか、加えないかの操作をして、求めた数を vector コンテナ result に格納して、最後に result を出力しています。

bit全検索として鍵になる行は、20、22、23行の操作となります。

本質的ではないですが、C で「1」と書くと、型 int を持ちます。多くの環境では、int は32ビットです。今回の問題は、260 まで範囲となるため、「1ULL」と接尾辞をつけて、unsinged long long であることを示さないと動作しません。C では、2項演算子で演算する前に左項と右項の型を合わせます。このため、いくつかの変数の型は、unsinged long long ではなく int にできます。ただし、このプログラムで使う整数型は、演算時の型変換を避けるため、unsinged long long にしました。

AtCoder は、問題ページから解答プログラムを提出できます。このプログラムは、AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC269C)

Python でも書いてみました。C++ をそのまま Python に落とし込んだようなプログラムになっています。bit全検索のコーディングとしては、「1 << i」は、「i ** 2」とも書けます。C++ のコーディング例に合わせて、シフト演算を採用しました。これが Python らしいプログラムか、判断できません。

"""AtCoder Beginner Contest 269 C"""
n = int(input())
p = []
for i in range(64):
    if n & (1 << i):
        p.append(i)

result = []
for bit in range(1 << len(p)):
    n = 0
    for i in range(len(p)):
        if bit & (1 << i):
            n = n + (1 << p[i])
    result.append(n)

print(*result, sep="\n")

Python 版も「AC」と判定されました。

2022年11月28日 結果のリスト出力を Python らしく修正しました。

最後に

C問題については、かなり難しくなった印象です。bit全検索について知識がない場合、最初から考えて解くのは難しいと思います。

ABC269 について、引き続き、D問題まで紹介します。

COMMENT

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

CAPTCHA