AtCoder

ABC301 D問題(Bitmask)を解く

AtCoder_ABC301_D

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

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

D問題 Bitmask(Difficulty : 885)

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

ABC301 D問題 Bitmask

与えられた条件で2進数の最大値を求める問題です。AtCoder Problems による Difficulty は 885 でした。

解答案

文字列 S に含まれる ‘?’ を ‘1’ または ‘0’ に置き換えて、2進数として N 以下で最大の数を求めます。’?’ は、最大で60個あるため、すべての場合をビット全探索を行うことは難しいです。

以下は、公式解説を参考にしました。

この問題は、上の桁から ‘?’ の値を決めることができます。

  • 一番上の ‘?’ を ‘1’ にして、それより下の桁を ‘0’ にする。それを2進数としてみたときに、N 以下であれば、元の ‘?’ は ‘1’ に確定することができます。逆に N を超えれば、’0′ に確定することができます。
  • 上の桁から以上の方法で、’1′ か ‘0’ を確定していきます。
  • 最終的に得られた2進数が N を超えれば -1 を出力します。N 以下であれば、その数を出力します。

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

2進数文字列を10進数に変換する関数は自作のライブラリを使いました。関数 Kto10 は、string 文字列と基底(2~9)を与えることができます(6-14行目)。

プログラムの本体では、while 文で ‘?’ を処理します。元の文字列 s を一時変数 t にコピーして、上位の桁から ‘?’ を上記の考察に従い処理していきます。一番上位の桁は、’1′ か ‘0’ に確定するため、元の文字列 s を更新します(36-40行目)。

‘?’ がすべて確定したら、while 文を抜けて、文字列を変換して N より大きければ、-1 をそれ以外の場合は、変換した数字を出力します。

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

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

typedef unsigned long long int ull;

ull Kto10(string s, int k) {
	ull result = 0;

	for (int i = 0; i < s.length(); ++i) {
		result = result * k + (s[i] - '0');
	}

	return result;
}

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

	int size = s.length();
	bool changed = true;
	while (changed) {
		string t = s;
		changed = false;
		for (int i = 0; i < size; ++i) {
			if (t[i] == '?') {
				t[i] = '1';
				for (int j = i + 1; j < size; ++j) {
					if (t[j] == '?') {
						t[j] = '0';
					}
				}
				if (n >= Kto10(t, 2)) {
					s[i] = '1';
				} else {
					s[i] = '0';
				}
				changed = true;
			}
		}
	}

	ull result = Kto10(s, 2);
	if (n < result) {
		cout << -1 << endl;
	} else {
		cout << result << endl;
	}

	return 0;
}

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

Python プログラム例(ABC301D)

Python 版は、C++ を移植しました。文字列を書き換えることができないため、文字列を再生成しています(21、24、26、28行目)。もっとよい書き方ができるかもしれません。

"""AtCoder Beginner Contest 301 D"""


def Kto10(s, k):
    result = 0
    for i in range(len(s)):
        result = result * k + (ord(s[i]) - ord('0'))
    return result


s = input()
n = int(input())

size = len(s)
changed = True
while changed:
    t = s
    changed = False
    for i in range(size):
        if t[i] == '?':
            t = t[:i] + '1' + t[i + 1:]
            for j in range(i + 1, size):
                if t[j] == '?':
                    t = t[:j] + '0' + t[j + 1:]
            if n >= Kto10(t, 2):
                s = s[:i] + '1' + s[i + 1:]
            else:
                s = s[:i] + '0' + s[i + 1:]
            changed = True

result = Kto10(s, 2)
if n < result:
    result = -1
print(result)

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

最後に

この問題は、コンテスト中は最後までWAが取り切れませんでした。解説を読み、今回の解説を書きました。今度、似た問題を解けるようになればと思います。

引き続き ABC に挑戦して、解説記事を書いていくつもりです。

COMMENT

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

CAPTCHA