Official

B - Extended ABC Editorial by MMNMM

この問題はいくつかの方針で解くことができます。

  1. 拡張 ABC 文字列の定義に従って判定を行う方法
    • 素直な方法
    • 少し工夫をする方法
    • より工夫をする方法
  2. 拡張 ABC 文字列が満たす条件を使って判定を行う方法
    • 方法 1
    • 少し工夫をする方法
    • より工夫をする方法
  3. 正規表現を用いて判定を行う方法

それぞれの方針について解説します。
実装例は C++ と Python のものがあります。 上にある方針のほうが考察が少なく、文法的にも平易な実装例ですが、下にある方針のほうが実装の量は比較的少ないです。

1. 拡張 ABC 文字列の定義に従って判定を行う方法

1-1. 素直な方法

拡張 ABC 文字列であることの定義は「ある拡張 A 文字列 \(S _ A\) 、拡張 B 文字列 \(S _ B\) 、拡張 C 文字列 \(S _ C\) が存在して、\(S _ A,S _ B,S _ C\) をこの順に連結した文字列が \(S\) と等しい」ことでした。 文字列を連結しても文字列の長さは減らないので、この条件で使われる拡張 A 文字列の長さは \(0\) 以上 \(100\) 以下です（B, C についても同様です）。

よって、ありえる文字列 \(S _ A,S _ B,S _ C\) の組み合わせ \(101 ^ 3\) 通りをすべて試し、与えられた文字列 \(S\) と等しいかどうか判定を行うことでこの問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <string>

using namespace std;

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

    for (int a = 0; a <= 100; ++a) {
        for (int b = 0; b <= 100; ++b) {
            for (int c = 0; c <= 100; ++c) {
                // a 文字の A と b 文字の B と c 文字の C を連結したものが S と等しければ Yes
                if (string(a, 'A') + string(b, 'B') + string(c, 'C') == S) {
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }

    // 等しくなるようなものがなければ No
    cout << "No" << endl;
    return 0;
}

S = input()

for a in range(0, 101):
    for b in range(0, 101):
        for c in range(0, 101):
            # a 文字の A と b 文字の B と c 文字の C を連結したものが S と等しければ Yes
            if 'A' * a + 'B' * b + 'C' * c == S:
                print('Yes')
                exit()

# 等しくなるようなものがなければ No
print('No')

1-2. 少し工夫をする方法

文字列の長さを絶対値記号 \(|\cdot|\) で表します。

結合したときの長さが \(|S|\) である必要があるため、\(S _ A,S _ B\) の候補を決めたとき、\(S _ C\) としては長さ \(|S|-|S _ A|-|S _ B|\) のものだけ考えればよいです。 これが \(0\) 以上である必要があるため、\(S _ B\) も長さが \(0\) 以上 \(|S|-|S _ A|\) 以下のものだけ考えればよいです。 同様に \(S _ A\) の長さも \(|S|\) 以下のものを考えればよいです。

この考察を行うことで、より高速に判定を行うことができます。

実装例は以下のようになります。

#include <iostream>
#include <string>

using namespace std;

int main() {
    string S;
    cin >> S;
    
    int N = S.size();

    for (int a = 0; a <= N; ++a) {
        for (int b = 0; b <= N - a; ++b) {
            int c = N - a - b;
            if (S == string(a, 'A') + string(b, 'B') + string(c, 'C')) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
    return 0;
}

S = input()
N = len(S)

for a in range(0, N + 1):
    for b in range(0, N - a + 1):
        c = N - a - b
        if 'A' * a + 'B' * b + 'C' * c == S:
            print('Yes')
            exit()

print('No')

1-3. より工夫をする方法

\(S _ A\) の長さを次のような値で決め打ってしまっても正しく判定できることが証明できます。

  • \(S\) に含まれる A の個数
  • \(S\) に先頭から連続して含まれる A の個数
  • \(S\) のうち最後に出現する A の位置

証明

答えが No である場合、どのような拡張 A 文字列 \(S _ A\) をとっても正しく判定を行うことができます（\(S\) が拡張 ABC 文字列ではないので、条件を満たす \(S _ A,S _ B,S _ C\) は存在しません）。

よって、答えが Yes であるときに使うべき \(S _ A\) を正しく求められればよいです。 上の値は、どれも答えが Yes のときには \(S _ A\) の長さと等しくなるため、これらの値を使って判定を行っても正しく判定できることがわかります。

同様に、\(S _ B\) の長さや \(S _ C\) の長さとして

  • \(S\) に含まれる B, C の個数
  • \(S\) に末尾から連続して含まれる C の個数

のような値で決め打つことができます。

これらの値をもとに判定を行うことで、より高速に判定を行うことができます。

実装例は以下のようになります。 この実装例では、\(S _ A,S _ B,S _ C\) の長さとして \(S\) に含まれる A, B, C の個数を用いています。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

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

    int a = ranges::count(S, 'A');
    int b = ranges::count(S, 'B');
    int c = ranges::count(S, 'C');

    if (S == string(a, 'A') + string(b, 'B') + string(c, 'C')) {
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;
    return 0;
}

S = input()

a = S.count('A')
b = S.count('B')
c = S.count('C')

if 'A' * a + 'B' * b + 'C' * c == S:
    print('Yes')
    exit()

print('No')

2. 拡張 ABC 文字列が満たす条件を使って判定を行う方法

2-1. 方法 1

A, B, C からなる文字列 \(S\) が拡張 ABC 文字列であることと、次の条件は同値です。

  • \(S\) に含まれるすべての B について、それより後には B もしくは C しか含まれない。
  • \(S\) に含まれるすべての C について、それより後には C しか含まれない。

（A の前や B の前に関する条件を付け加える必要はありません。「\(x\) の後に \(y\) がある」という条件を読み替えると「\(y\) の前に \(x\) がある」という形にできるためです。）

この条件を用いて判定を行うことで、この問題を解くことができます。 「すべてについて」という形式の条件なので、条件を満たさなかったときに No を出力して終了し、何事もなければ Yes を出力する形で実装を行うとシンプルに実装できます。

実装例は以下のようになります。

#include <iostream>
#include <string>

using namespace std;

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

    int N = S.size();

    for (int i = 0; i < N; ++i) {
        if (S[i] == 'B') {
            // B の後にあるのは B か C のみでなければならない
            for (int j = i + 1; j < N; ++j) {
                if (S[j] != 'B' && S[j] != 'C') {
                    // 条件を満たさなければ No
                    cout << "No" << endl;
                    return 0;
                }
            }
        } else if (S[i] == 'C') {
            // C の後にあるのは C のみでなければならない
            for (int j = i + 1; j < N; ++j) {
                if (S[j] != 'C') {
                    // 条件を満たさなければ No
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    }

    cout << "Yes" << endl;
    return 0;
}

S = input()

for i, c in enumerate(S):
    if c == 'B':
        # B の後にあるのは B か C のみでなければならない
        for d in S[i+1:]:
            if d != 'B' and d != 'C':
                # 条件を満たさなければ No
                print('No')
                exit()
    elif c == 'C':
        # C の後にあるのは C のみでなければならない
        for d in S[i+1:]:
            if d != 'C':
                # 条件を満たさなければ No
                print('No')
                exit()

print('Yes')

2-2. 少し工夫をする方法

実は、2-1 で考えた条件の「それより後」を「直後」に変えても正しく判定を行うことができます。

証明

答えが Yes のとき、判定を間違えることはありません。

答えが No のとき、2-1 のプログラムが No を出力したときに見ている文字のペアについて考えます。 ありえる文字のペア \((\)B\(,\)A\(),(\)C\(,\)A\(),(\)C\(,\)B\()\) の \(3\) 通りについて場合分けを行うことで、後ろにある方とその直前の組が条件を満たしていないことを示すことができます。

よって、これを用いることでより高速に判定を行うことができます。

実装例は以下のようになります。

#include <iostream>
#include <string>

using namespace std;

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

    int N = S.size();

    for (int i = 0; i + 1 < N; ++i) {
        if (S[i] == 'B' && S[i + 1] != 'B' && S[i + 1] != 'C') {
            // B の直後にあるのは B か C のみでなければならない
            // 条件を満たさなければ No
            cout << "No" << endl;
            return 0;
        } else if (S[i] == 'C' && S[i + 1] != 'C') {
            // C の直後にあるのは C のみでなければならない
            // 条件を満たさなければ No
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

S = input()

for c, d in zip(S, S[1:]):
    if c == 'B' and d != 'B' and d != 'C':
        # B の直後にあるのは B か C のみでなければならない
        # 条件を満たさなければ No
        print('No')
        exit()
    elif c == 'C' and d != 'C':
        # C の直後にあるのは C のみでなければならない
        # 条件を満たさなければ No
        print('No')
        exit()

print('Yes')

2-3. より工夫をする方法

2-2 で使った条件を言い換えると、「連続する \(2\) つの文字は、アルファベット順で等しいか、後ろのほうがアルファベット順でもより後にある」ということになります。

これは、「文字列に含まれる文字がアルファベット順でソートされている」とさらに言い換えることができます。

この条件を用いてこの問題を解くことができます。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

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

    if (ranges::is_sorted(S)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

S = input()

if ''.join(sorted(S)) == S:
    print('Yes')
else:
    print('No')

3. 正規表現を用いて判定を行う方法

拡張 ABC 文字列を表す正規表現は A*B*C* です。

文字列が正規表現にマッチするかを判定する機能がある言語においては、それを用いることでこの問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <string>
#include <regex>

using namespace std;

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

    if (regex_match(S, regex("A*B*C*"))) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

from re import fullmatch

if fullmatch('A*B*C*', input()):
    print('Yes')
else:
    print('No')

posted:
last update: