Official
B - Piano Editorial by yuto1115
解説\(S\) の長さ \(W+B\) の部分文字列を全探索し、それぞれについてその部分文字列に含まれる w
と b
の数が条件と一致しているか確認すればよいです。\(S\) の長さ \(W+B\) の部分文字列はある正整数 \(l\) を用いて \(S_lS_{l+1}\dots S_{l+W+B-1}\) と表されますが、この \(l\) を全探索することはできません。そこで、以下の性質を用います。
- \(l_1\) と \(l_2\) を \(12\) で割った余りが等しいとき、\(S\) の \(l_1\) 文字目から始まる長さ \(W+B\) の部分文字列と、\(S\) の \(l_2\) 文字目から始まる長さ \(W+B\) の部分文字列は、文字列として等しい。(なお、\(12\) は \(S\) の繰り返し単位
wbwbwwbwbwbw
の長さに該当する。)
よって、\(l\) としては \(1,2,\dots,12\) のみを調べればよいため、\(12(W+B)\) 回程度の計算でこの問題を解くことができます。
実装例 (C++) :
#include <bits/stdc++.h>
using namespace std;
const string t = "wbwbwwbwbwbw";
int main() {
int w, b;
cin >> w >> b;
for (int i = 0; i < (int) t.size(); i++) {
int nw = 0, nb = 0;
for (int j = 0; j < w + b; j++) {
if (t[(i + j) % t.size()] == 'w') ++nw;
else ++nb;
}
if (w == nw and b == nb) {
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
}
実装例 (Python) :
t = "wbwbwwbwbwbw"
w, b = map(int, input().split())
for i in range(len(t)):
nw = 0
nb = 0
for j in range(w + b):
if t[(i + j) % len(t)] == 'w':
nw += 1
else:
nb += 1
if w == nw and b == nb:
print("Yes")
exit(0)
print("No")
posted:
last update: