Official

B - Piano Editorial by yuto1115

解説

\(S\) の長さ \(W+B\) の部分文字列を全探索し、それぞれについてその部分文字列に含まれる wb の数が条件と一致しているか確認すればよいです。\(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: