Official
B - Triple Metre Editorial by Nyaan
この問題はいくつか解法が考えられます。順にみていきましょう。
まず、問題文通りの解法として「 \(T\) を実際に構築して \(T\) の部分文字列に \(S\) が含まれるかを調べる」という方法があります。
たとえば Python では str 型のオブジェクト S
,T
に対して S in T
で T
の部分文字列に S
を含むかを判定することができます。
Python による実装例は次の通りです。
S = input()
T = "oxx" * 10 ** 5
print("Yes" if S in T else "No")
Python は計算量を仕様として規定していないので上の実装例は厳密には計算量不明ですが、 例えば AtCoder で言語に Python 3.8.2 を選んで提出した時に選択される処理系 (CPython) では Boyer-Moore 法などにより \(\mathrm{O}(|S| + |T|)\) で計算するアルゴリズムが実装されているので \(\mathrm{O}(|S| + |T|)\) と考えてよさそうです。
次に、考察により計算量を落とした解法を紹介します。
条件を満たす文字列は次の \(3\) 個の条件のいずれかを満たします。
- \(i\) を \(3\) で割った余りが \(0\) のときは
S[i] = 'o'
で、それ以外はS[i] = 'x'
である。 - \(i\) を \(3\) で割った余りが \(1\) のときは
S[i] = 'o'
で、それ以外はS[i] = 'x'
である。 - \(i\) を \(3\) で割った余りが \(2\) のときは
S[i] = 'o'
で、それ以外はS[i] = 'x'
である。
よって、\(S\) がこの条件を満たすかを for ループなどを用いて判定すれば、この問題を \(\mathrm{O}(|S|)\) で解くことができます。
C++ による実装例は次の通りです。
#include <iostream>
#include <string>
using namespace std;
int main() {
string S;
cin >> S;
for (string T : {"oxx", "xox", "xxo"}) {
bool ok = true;
for (int i = 0; i < (int)S.size(); i++) {
if (T[i % 3] != S[i]) ok = false;
}
if (ok) {
cout << "Yes" << endl;
exit(0);
}
}
cout << "No" << endl;
}
posted:
last update: