AOJ 2369 CatChecker - NOSSの雑記

問題概要

文字列Sが与えられる。Sが猫の鳴き声か判定したい。猫の鳴き声は次のように定義される。

空文字列""は猫の鳴き声
X,Yが猫の鳴き声ならば、'm'+X+'e'+Y+'w'は猫の鳴き声
以上で定義されるものだけが猫の鳴き声

Sが猫の鳴き声ならば"Cat"そうでなければ"Rabbit"と出力せよ。

制約

1 ≦ |S| ≦ 500
Sは'm','e','w'のみを含む

解法

Sの部分文字列が猫の鳴き声のとき、そこを空文字列に置き換えてもSが猫の鳴き声かどうかは変わりません。なのでSの猫の鳴き声の部分を消去していって簡単に判定できるものまで小さくすればよいです。つまり、消去していって最終的な状態が"mew"になっていれば猫の鳴き声です。

消すときは'm'+X+'e'+Y+'w'を守るように、"mmewe"を"me"に、"emeww"を"ew"に置換するようにします。

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, cat1 = "mmewe", cat2 = "emeww";
    cin >> s;
    while(1){
        int pos;
        pos = s.find(cat1);
        if(pos!=s.npos){
            s.replace(pos,cat1.size(),"me");
            continue;
        }
        pos = s.find(cat2);
        if(pos!=s.npos){
            s.replace(pos,cat2.size(),"ew");
            continue;
        }
        break;
    }
    cout << (s=="mew"?"Cat":"Rabbit") << endl;
    return 0;
}