AtCoder が提供しているABC（AtCoder Beginner Contest）269 のC問題をC++とPythonで解いてみました。ABC269は、2022年9月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Submask（Difficulty : 384）
問題はリンク先をご覧ください。
問題から読み取りにくいかもしれませんが、bit全検索を使う典型問題です。AtCoder Problems による Difficulty は、384 でした。
解答案
問題を解く方針を書きだします。
- 自然数 N を標準入力から読み取る。
- N を2進数で表現したときに、1が立っている場所を調べる。
- N の１が立っているそれぞれの場所で、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行の操作となります。
本質的ではないですが、Ｃ で「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全検索について知識がない場合、最初から考えて解くのは難しいと思います。
引き続き ABC の問題を紹介していきます。
