AtCoderログ：0085 - ABC 049 C

# 問題

https://atcoder.jp/contests/abc049/tasks/arc065_a

## 問題文
> 英小文字からなる文字列 $S$ が与えられます。$T$ が空文字列である状態から始め、以下の操作を好きな回数繰り返すことで $S=T$ とすることができるか判定してください。
> ・$T$ の末尾に dream dreamer erase eraser のいずれかを追加する。

## 制約
> ・$1 \le |S| \le 10^5$
> ・$S$ は英小文字からなる。

## 収録されている問題セット
- [AtCoder に登録したら次にやること](https://qiita.com/drken/items/fd4e5e3630d0f5859067) ([第09問](https://qiita.com/drken/items/fd4e5e3630d0f5859067#%E7%AC%AC-9-%E5%95%8F--abc-049-c---daydream-300-%E7%82%B9))

- [AtCoder Beginners Selection](https://atcoder.jp/contests/abs)

# 回答
## 回答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 を出力して終了となります。

```C++:abc049c-1.cpp
#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' の冒頭から調べるのがとても簡単になります。コードは以下のようになりました。

```C++:abc049c-2.cpp
#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 に登録したら次にやること](https://qiita.com/drken/items/fd4e5e3630d0f5859067) → [第09問の解説](https://qiita.com/drken/items/fd4e5e3630d0f5859067#%E7%AC%AC-9-%E5%95%8F--abc-049-c---daydream-300-%E7%82%B9)
回答2と同じ方針でした。

## [AtCoder の解説](https://atcoder.jp/contests/abc049/tasks/arc065_a/editorial) → [公式解説](https://img.atcoder.jp/arc065/editorial.pdf)
回答2と同じ方針でした。

# リンク
## 前後の記事
- 前の記事 → [AtCoderログ：0084 - ABC 121 B](https://qiita.com/RoadLynton/items/9b497e46c54e66494c19)
- 次の記事 → [AtCoderログ：0086 - パナソニックプログラミングコンテスト2020 B](https://qiita.com/RoadLynton/items/b6e3bc9f1803375b0746)