ABC337-B 解説

B - Extended ABC

解法1 隣接する部分だけ見る方法

$S$ の隣接する2文字を見ます。これがAA,AB,AC,BB,BC,CCのいずれかならば$S$は拡張ABC文字列です。逆に言うと、BA,CA,CBのいずれかが含まれていると$S$は拡張ABC文字列ではありません。

S = input()
for i in range(len(S) - 1):
    if S[i: i + 2] in ["BA", "CA", "CB"]:
        print("No")
        exit()
print("Yes")

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

int main() {
    string S;
    cin >> S;
    for (int i = 0; i < S.size() - 1; i++) {
        if ((S[i] == 'B' && S[i + 1] == 'A') || (S[i] == 'C' && (S[i + 1] == 'A' || S[i + 1] == 'B'))) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
}

解法2

解法1をよく見つめてみましょう。BA,CA,CBは、全て1文字目が0文字目よりも小さくなっています。逆に言うと、全ての長さ2の部分列に対して1文字目が0文字目以上であるかどうかを判定すれば解けます。

S = input()
print("Yes" if all(S[i] <= S[i + 1] for i in range(len(S) - 1)) else "No")

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

int main() {
    string S;
    cin >> S;
    bool ok = true;
    for (int i = 0; i < S.size() - 1; i++) {
        if (S[i] > S[i + 1]) ok = false;
    }
    cout << (ok ? "Yes\n" : "No\n");
}

解法3

解法2をよく見つめてみましょう。全ての長さ2の部分列に対して1文字目が0文字目以上であることは、ソートされていることと同値です。

S = input()
print("Yes" if list(S) == list(sorted(S)) else "No")

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

int main() {
    string S;
    cin >> S;
    string T = S;
    sort(T.begin(), T.end());
    cout << (S == T ? "Yes\n" : "No\n");
}

解法4 ランレングス圧縮する

ランレングス圧縮とは、同じ文字が続いている部分をまとめる圧縮方法です。今回は、まとめた部分の文字数は必要ないので、文字列だけ持ちます。ただし、C++にはuniqueという重複削除の関数があるのでこれを使うと簡単です。

S = input()
T = ""
i = 0
while i < len(S):
    j = i
    while j < len(S) and S[i] == S[j]:
        j += 1
    T += S[i]
    i = j
print("Yes" if T == "AC" or T in "ABC" else "No")

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

int main() {
    string S;
    cin >> S;
    S.erase(unique(S.begin(), S.end()), S.end());
    for (string T: {"A", "B", "C", "AB", "AC", "BC", "ABC"}) {
        if (S == T) {
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
}

解法5 最初から見ていく

最初$i=0$として、$S_i=$Aである間$i$を進め、$S_i=$Bである間$i$を進め、$S_i=$Cである間$i$を進めて、$i=|S|$になれば$S$は拡張ABC文字列です。

S = input()
i = 0
while i < len(S) and S[i] == 'A':
    i += 1
while i < len(S) and S[i] == 'B':
    i += 1
while i < len(S) and S[i] == 'C':
    i += 1
print("Yes" if i == len(S) else "No")

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

int main() {
    string S;
    cin >> S;
    int i = 0;
    while (i < S.size() && S[i] == 'A') {
        i++;
    }
    while (i < S.size() && S[i] == 'B') {
        i++;
    }
    while (i < S.size() && S[i] == 'C') {
        i++;
    }
    cout << (i == S.size() ? "Yes\n" : "No\n");
}

解法6 正規表現を使う解法

拡張ABC文字列は、正規表現ABC*にマッチします。これを判定すれば解けます。

import re
print("Yes" if re.search(r"^A*B*C*$", input()) else "No")

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

int main() {
    string S;
    cin >> S;
    regex reg{R"(^A*B*C*$)"};
    smatch m;
    cout << (regex_search(S, m, reg) ? "Yes\n" : "No\n");
}

Sed

/^A*B*C*$/cYes
cNo