問題
問題文
英小文字からなる文字列 $S$ が与えられます。$T$ が空文字列である状態から始め、以下の操作を好きな回数繰り返すことで $S=T$ とすることができるか判定してください。
・$T$ の末尾に dream dreamer erase eraser のいずれかを追加する。
制約
・$1 \le |S| \le 10^5$
・$S$ は英小文字からなる。
収録されている問題セット
回答
回答1 (AC)
与えられた文字列 $S$ を先頭から調べてみます。先頭に "eraser" という文字列があれば、それは eraser として確定できます。先頭が eraser ではないことが確定した状態で戦闘に "erase" という文字列があれば、それは erase として確定できます。この順番はとても重要で、逆に先頭に "erase" という文字列を見つけても、これは erase なのか eraser (の一部)なのかを確定することが出来ません。
同様に dreamer と dream についても調べるのですが、ちょっとややこしくなります。先頭に dreamer という文字列があったとしても、それは dreamer である可能性と、dream + er... である可能性があります。dreamer であることが確定できるのは、先頭の文字列が dreamerd 又は dreamere の場合です。同様に、先頭からの文字列が dreamd または dreame の場合には dream であることが確定出来ます。なお、このままでは s="dreamer" または s="dream" の場合を検出できないので、条件式に追加する必要があります。
以上をまとめたコードは以下のようになりました。文字列 s に対し、ss にコピーを保持し、文字列 s の先頭が eraser/erase/dreamer/dream であるかを判別し、そうである場合には s から先頭部分を削除しています。一通りのチェックが終わった段階で文字列 s に変化がない (つまり s=ss) の場合には、NO と出力して終了します。文字列 s がだんだん短くなり、s="" となるまで削除できれば YES を出力して終了となります。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
string answer = "YES";
while ( s!="" ) {
string ss = s;
if ( s.find("eraser")==0 ) {
s = s.erase(0,6);
} else if ( s.find("erase")==0 ) {
s = s.erase(0,5);
} else if ( s=="dream" || s=="dreamer" ) {
s = "";
} else if ( s.find("dreamerd")==0 || s.find("dreamere")==0 ) {
s = s.erase(0,7);
} else if ( s.find("dreamd")==0 || s.find("dreame")==0 ) {
s = s.erase(0,5);
}
if ( ss==s ) {
answer = "NO";
break;
}
}
cout << answer << endl;
}
回答2 (AC)
この問題のややこしい点は、使用している $4$ 種類の文字列 erase/eraser/dream/dreamer がお互いに似ているところです。そこで、これら文字列を逆から考えることにすると、文字列 s を逆順にした文字列 s' が esare/resare/maerd/remaerd という文字列からだけで構成できるか？を調べれば良いことになります。ありがたいことに新しい4つの文字列は文字の並びの重複が少ないので、文字列 s' の冒頭から調べるのがとても簡単になります。コードは以下のようになりました。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
string answer = "YES";
while ( s!="" ) {
string ss = s;
if ( s.find("esare")==0 || s.find("maerd")==0 ) {
s = s.erase(0,4);
} else if ( s.find("resare")==0 ) {
s = s.erase(0,5);
} else if ( s.find("remaerd")==0 ) {
s = s.erase(0,6);
}
if ( ss==s ) {
answer = "NO";
break;
}
}
cout << answer << endl;
}
調べたこと
AtCoder に登録したら次にやること → 第09問の解説
回答2と同じ方針でした。
AtCoder の解説 → 公式解説
回答2と同じ方針でした。