【AtCoder】ABC 337 B - Extended ABC | 茶コーダーが解くAtCoder

atcoder.jp

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

問題概要

「拡張 A 文字列」「拡張 B 文字列」「拡張 C 文字列」および「拡張 ABC 文字列」を以下のように定義する。

• 文字列 が拡張 A 文字列である。 の全ての文字がAである。
• 文字列 が拡張 B 文字列である。 の全ての文字がBである。
• 文字列 が拡張 C 文字列である。 の全ての文字がCである。
• 文字列 が拡張 ABC 文字列である。 が、ある拡張 A 文字列 、ある拡張 B 文字列 、ある拡張 C 文字列 をこの順に連結してできる文字列である。

A, B, Cからなる文字列 が与えられるので、それが拡張 ABC 文字列であるかを判定せよ。ただし、空文字列は拡張 A 文字列でも拡張 B 文字列でも拡張 C 文字列でもあることに注意すること。

制約

• 入力はすべて整数。
• の長さは1以上100以下。

考察

色々な実装が考えられそうなので、ここではその一例を示す。

上述の4つの定義から、拡張 ABC 文字列において以下が成り立つことが分かる。

• 先頭はA, B, Cいずれかである。
• Aの次の文字はA, B, Cのいずれかである。
• Bの次の文字はB, Cのいずれかである。
• Cの次の文字はCである。

上二つの条件は制約下で常に成り立つので、下二つについて がこれらの条件を満たすかを判定すればよい。

これは前にも書いたが、条件合致判定の問題は「成り立たないと分かった時点で処理を打ち切る」と考えやすくなる。

コード

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

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

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

int main()
{
    string S;
    cin >> S;

    rep(i, 0, S.size() - 1)
    {
        if (S[i] == 'B')
        {
            if (S[i + 1] == 'A')
            {
                cout << "No" << endl;
                return 0;
            }
        }
        else if (S[i] == 'C')
        {
            if (S[i + 1] == 'A' || S[i + 1] == 'B')
            {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

atcoder.jp

実装時間: 5分以内