AtCoder が提供しているABC（AtCoder Beginner Contest）301 のD問題をC++とPythonで解いてみました。ABC301は、2023年5月13日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Bitmask（Difficulty : 885）
問題はリンク先をご覧ください。
与えられた条件で2進数の最大値を求める問題です。AtCoder Problems による Difficulty は 885 でした。
解答案
文字列 S に含まれる ‘?’ を ‘1’ または ‘0’ に置き換えて、2進数として N 以下で最大の数を求めます。’?’ は、最大で60個あるため、すべての場合をビット全探索を行うことは難しいです。
以下は、公式解説を参考にしました。
この問題は、上の桁から ‘?’ の値を決めることができます。
- 一番上の ‘?’ を ‘1’ にして、それより下の桁を ‘0’ にする。それを2進数としてみたときに、N 以下であれば、元の ‘?’ は ‘1’ に確定することができます。逆に Ｎ を超えれば、’0′ に確定することができます。
- 上の桁から以上の方法で、’1′ か ‘0’ を確定していきます。
- 最終的に得られた2進数が N を超えれば -1 を出力します。Ｎ 以下であれば、その数を出力します。
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 の問題を紹介していきます。
