【AtCoder】ABC 346 B - Piano | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 251

問題概要

文字列wbwbwwbwbwbwを無限に繰り返してできる文字列を とする。 の連続部分文字列であって、 個のwと 個のbからなるものが存在するかを判定せよ。

制約

• は整数
• 
• 

考察

を無限個結合した文字列 を考える。条件を満たす連続部分文字列を探すので、まずは始点の全探索をしよう。 の周期は12なので、12通りの始点が考えられる。

次に、 の各文字の判定をすることになるが、 は無限に続くのでどこかで打ち切らなければならない。ここでポイントなのが、 にはwとbしか現れない点だ。つまり、 の 文字目までを探索して条件に合致しなければ打ち切ってしまえばいい。

実装においては に対して探索をしても良いし、 の周期が12なので、インデックスを12の剰余で扱ってもよい。

コード

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

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

int main()
{
    int W, B;
    cin >> W >> B;
    string S = "wbwbwwbwbwbw";
    int l = S.size();

    rep(i, 0, l)
    {
        int w_cnt = 0, b_cnt = 0;
        rep(j, 0, W + B)
        {
            if (S[(i + j) % l] == 'w')
                w_cnt++;
            else
                b_cnt++;
        }

        if (w_cnt == W && b_cnt == B)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
}

atcoder.jp

実装時間: 15分