AtCoder

ABC306 B問題(Base 2)を解く

AtCoder_ABC306_B

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

この回は、コンテスト中にジャッジ遅れが大きく発生したため、unrated となりました。

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

B問題 Base 2

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

ABC306 B問題 Base 2

64ビット整数を計算する問題です。AtCoder Problems による Difficulty は算出されていません。B問題としては,やや難しいかもしれません。

解答案

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

0または1からなる64項の数列が与えられます。これを64ビット整数に変換する問題です。

AtCoderの環境(というより多くの環境)では、int は32ビットです。long long は64ビット整数ですが、符号付きの場合は、最上位ビットが符号になるため unsigned long long 型(または、unsigned long 型)を使う必要があります(8行目)。

C言語の整数の大きさについては、この記事で説明しています。

変数 result の初期値は、unsigned long long の定数とするために、「ULL」を付けていますが、これにより識別子のように見えるかもしれません。もちろん右辺を単に「0」と書いてもよいです。

プログラム本体では、ビットをシフトして計算します(9ー13行目)。

以下が、C++プログラムとなります。

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

typedef unsigned long long int ull;

int main()
{
	ull result = 0ULL;
	for (int i = 0; i < 64; ++i) {
		ull a;
		cin >> a;
		result += a << i;
	}

	cout << result << endl;

	return 0;
}

bitset クラスの紹介

C++ の標準ライブラリ bitset クラスを使えば、コンストラクタを通じて、0 と 1 から成る string 文字列を bitset クラスとして変換できます(16行目)。逆にメソッド to_ullong で unsigned long long に変換できます(18行目)。

普段は、bits/stdc++.h をインクルードしていますが、この問題は、最低限のヘッダファイルだけインクルードしました(1ー3行目)。

AOJ が提供しているコース ITP2 のトピック#10で bitset クラスを扱っています。主な演算子とクラスは、こちらの記事で紹介しています。

#include <iostream>
#include <string>
#include <bitset>

using namespace std;

int main()
{
	string s = "";
	for (int i = 0; i < 64; ++i) {
		char a;
		cin >> a;
		s = a + s;
	}

	bitset<64> result(s);

	cout << result.to_ullong() << endl;

	return 0;
}

どちらも、AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC306B)

Python は、整数の大きさに上限がありません。このため、C++ のように型の大きさを心配する必要がありません。プログラムは、すっきりと書けました。

"""AtCoder Beginner Contest 306 B"""
a = list(map(int, input().split()))

result = 0
for i in range(64):
    result += a[i] << i

print(result)

こちらも「AC」と判定されました。

最後に

整数の型の大きさを理解する必要がある64ビット整数は、B問題としては難しいと思います。ただし、内容は、0と1から64ビット整数を計算させる教育的な問題でした。

ABC306 について、引き続き問題を紹介していきます。

COMMENT

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

CAPTCHA