読者です 読者をやめる 読者になる 読者になる

AOJ2369 CatChecker

解法
BNFが与えられるので、そのとおりに実装する。ただし substr() で時間がかかるためメモ化する。
BNFの実装方法は、自分は 'e' の位置を全て調べて正しい構文かどうかを再帰で繰り返し判定し、一つでも正しいパターンがあればその文字列はBNFによって正しく記述されているとした。

反省
はじめに提出したACコードは substr() してる辺りに無駄なコードがあって煩雑になってた。

#include <bits/stdc++.h>  
using namespace std;
  
map<string, bool> memo;
  
bool parse(string s) {
  if(memo.find(s) != memo.end()) return memo[s];
  if(s == "") return 1;
  int const size = s.size();
  if(s[0] != 'm' || s[size-1] != 'w') return memo[s] = 0;
     
  for(int i=1; i<size; i++) {
    if(s[i] == 'e') {
      if(
        parse(s.substr(1, i-1))
        && parse(s.substr(i+1, size-i-2))
      ) return memo[s] = 1;
    }
  }
  return memo[s] = 0;
}
   
string CatChecker(string s) {
  return parse(s) ? "Cat" : "Rabbit"; 
}
   
int main() {
  string s; cin >> s;
     
  cout << CatChecker(s) << endl;
     
  return 0;
}