AtCoder が提供しているABC（AtCoder Beginner Contest）346 のB問題をC++とPythonで解いてみました。ABC346は、2024年3月23日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Piano（Difficulty : 251）
問題はリンク先をご覧ください。
調べる通り数は12通りとなります。AtCoder Problems による Difficulty は 251 でした。
解答案
調べる通り数は、与えられた文字列 ”wbwbwwbwbwbw” の長さである12通りとなります。これは、この文字列を繰り返した文字列を対象とするため、始点となる12通りで条件が成立しなければ、結果的に条件が成立しないことから分かります。
C++ プログラム例（ABC346B）
制約 $0 \leqq W, B \leqq 100$ であるため、調べる部分文字列の長さは最長でも200文字となります。また、前述の考察より12通り調べればよいため、与えられた文字列を20回連結して、240文字の文字列を生成しておけば、十分な長さであることが分かります。
最初のループで12通り、次のループで [left, left + w + b) の文字列に含まれる ‘W’ と ‘B’ の個数を確認しています。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int w, b;
cin >> w >> b;
string s = "wbwbwwbwbwbw";
string t = "";
for (int i = 0; i < 20; ++i) {
t += s;
}
bool result = false;
for (int left = 0; left < s.length(); ++left) {
int cw = 0;
int cb = 0;
for (int right = left; right < left + w + b; ++right) {
if (t[right] == 'w') {
++cw;
} else {
++cb;
}
}
if ((cw == w)&&(cb == b)) {
result = true;
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC346B）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 346 B"""
w, b = map(int, input().split())
s = "wbwbwwbwbwbw"
t = s * 20
result = False
for left in range(len(s)):
cw = 0
cb = 0
for right in range(left, left + w + b):
if t[right] == 'w':
cw += 1
else:
cb += 1
if cw == w and cb == b:
result = True
print("Yes" if result else "No")こちらも「AC」と判定されました。
最後に
問題文に「無限に繰り返してできる文字列」とあり、難しく感じた人がいるかもしれません。調べる文字列の長さの上限は、制約から分かります。また、与えられた文字列の長さが調べる通り数となることがポイントでした。
引き続き ABC の問題を紹介していきます。
