問題
英大文字からなる長さ の文字列
と、長さ
の文字列
が与えられる。
ここで、 # のみからなる長さ の文字列
に対して以下の作業を何回でも行えるとき、
を
に一致させられるか判定せよ。
の中から連続する
文字を選び、
で置き換える。
入力
まず最初の1行目に整数 が与えられる。
次の1行には文字列 が与えられる。
その次の1行には文字列 が与えられる。
条件
は英大文字からなる長さ
の文字列
出力
を
に一致させられるならば
Yes を、一致させられないならば No をそれぞれ出力すること。
解法
まず、問題文の操作の通りに、 ##...# の状態の文字列 から、
文字の
を順番に変換していき、
を目指すという方法を愚直に実装することはとても困難です。
というのも、
に
がどんどん上書きされていくため、「どの部分から操作を始めるべきなのか」「次の操作はどのようにすべきなのか」等の情報を手に入れることが非常に難しくなってしまいます。
（もし、そのような方法でACできるものがあればコメントなどで教えてください…！）
一方で、最終目標となる が与えられているため、逆に
から
を引いていき、
を目指すという方法があると考えられます。
ここで、問題の例となっている
ABCBABC,
ABC の場合について考えます。
この文字列 を
#...# にするには、
- 4文字目から6文字目の
ABCを###に変換する - 0文字目から2文字目の
ABCを###に変換する - 2文字目から4文字目の
#B#を###に変換する
という手順で変換することができます。 （コードを書くために、0-indexで記述しています。）
この手順を図にすると、以下のようになります。
この例から、 であるすべての整数
に対して、以下のいずれかが成立すれば、文字列
を
文字分だけ
# に変換することができると言えます。
文字目と
文字目が一致する
#である
以上から、 である整数
に対して、文字列
の
文字目から
文字目まで調べ上げ、条件を満たすならば
# に変換していく、という方法で判定を行えます。
しかし、この方法については、先頭から最後まで調べ上げていき、 # に変換された文字列についても先頭から最後まで調べ上げ、ということを愚直に繰り返すと、1回のループで約 箇所分を調べ、1回の探索で
文字分を調べ、最大で約
回分のループを行うため、
の計算量となってしまい、実行時間制限に間に合いません。
そこで、どの文字から探索を始めるのかということを考えます。
最初の1回目の変換については、文字列 の中には
# が含まれないため、 の中に
と一致する部分があるかどうかを探します。
例えば、 の
文字目から始まる部分が
と一致すると仮定します。
このとき、 の
文字目から
文字目までが
# に変換されるので、 の「
文字目から始まる部分」「
文字目から始まる部分」……「
文字目から始まる部分」の全
箇所が、新たに
# に変換できる可能性がある場所として生まれます。
これを図にすると以下のようになります。
以上から、 # に変換できた箇所が1箇所ごとに、 箇所が次の探索候補となります。
最終的には約
箇所を
# に変えていくため、このように探索箇所を限っていくことにより、 の計算量で調べ上げることができます。
この問題では の値は最大でも5であるので、これは実行時間制限に十分間に合うと言えます。
ソースコード
まずは、 文字目から
文字目までがすべて
# に変換できるかどうかをbool値で返す関数 check() を以下のように実装しました。
bool visited[int(2e5 + 5)]; // visited は true ならば i 文字目が # に変換されていることを表す bool check(int start) { // start が始点となる文字のindexを表す if (start < 0 || start + m - 1 >= n) { // start が負であったり、(start + m - 1) 文字目が n 以上であれば、s を探索できないので false を返す return false; } // t の 0 文字目から m - 1 文字目までについて調査する // このforループを抜けたら変換可能と判定する for (int i = 0; i < m; i++) { if (visited[start + i]) { // もし visited[start + i] が true ならば、#になっているので次の文字について調べる continue; } if (s[start + i] != t[i]) { // 文字が一致しないならば、false を返す return false; } } // forループを抜けたので、 # に変換可能ということを記録する for (int i = 0; i < m; i++) { visited[start + i] = true; } // 変換可能であるので、 true を返す return true; }
この check() が実装されている状態で、main() 関数に以下のように実装して、全て変換可能かどうかを調査する部分を作成しました。
int n, m; string s, t; bool visited[int(2e5 + 5)]; // visited は true ならば i 文字目が # に変換されていることを表す bool started[int(2e5 + 5)]; // started は true ならば i 文字目から (i + m - 1) 文字目までが既に # に変換されていることを表す queue<int> que; // 探索スタートとなるindexを順に保存するためのqueue int main() { // 値の入力 cin >> n >> m; cin >> s; cin >> t; // まずは、すべての i に対して部分列が t と一致するかを調べる for (int i = 0; i + m - 1 < n; i++) { if (check(i)) { // もし一致するならば、queueにそのインデックスを追加する que.push(i); started[i] = true; } } // queueが空になるまで、探索を行う while (!que.empty()) { int q = que.front(); que.pop(); // (q - m + 1) 文字目から (q + m - 1) 文字目までの文字について、それらを先頭とした場合に # に変換できるかを確認する // started[i] が true ならば、追加で探索する必要はないので無視する（既に探索されているため） for (int i = 1; i < m; i++) { // もし check(q + i) が true ならば、queueに (q + i) を追加する if (q + i < n && check(q + i) && !started[q + i]) { que.push(q + i); started[q + i] = true; } // もし check(q - i) が true ならば、queueに (q - i) を追加する if (q - i >= 0 && check(q - i) && !started[q - i]) { que.push(q - i); started[q - i] = true; } } } // すべての visited[i] が true ならば Yes を、そうでないならば No を出力する for (int i = 0; i < n; i++) { if (!visited[i]) { No(); return 0; } } Yes(); return 0; }
感想
個人的には文字列に関しての問題に苦手意識があるので、コンテストに出ている際にこの問題が出たら、対応できるか不安になりますね…。
