mayoko’s diary

プロコンとかいろいろ。

AOJ 2369 CatChecker

最近のんびり過ごしています。

解法

区間 dp をします。

dp[l][r] = (区間 [l, r) が猫の鳴き声文字列になっているか?)というのを判定します。

これは,

  • s[l] = 'm', s[r-1] = 'w'
  • s[m] = 'e' の時, dp[l+1][m-1], dp[m+1][r-1] も true

が成り立てば dp[l][r] も true です。

今回の場合は dfs で書いたほうが高速に処理できそうな気がしたのでメモ化再帰を使っています(メモ化再帰は関係ありそうなところしか dfs しないので)。

const int MAXN = 555;
string s;
int dp[MAXN][MAXN];

// [l, r)
bool dfs(int l, int r) {
	int& ret = dp[l][r];
	if (ret >= 0) return ret;
	if (r-l == 0) return ret = 1;
	if (s[l] != 'm' || s[r-1] != 'w') return ret = 0;
	ret = 0;
	for (int m = l+1; m < r-1; m++) {
		if (s[m] == 'e') {
			if (dfs(l+1, m) && dfs(m+1, r-1)) {
				return ret = 1;
			}
		}
	}
	return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s;
    memset(dp, -1, sizeof(dp));
    if (dfs(0, s.size())) cout << "Cat" << endl;
    else cout << "Rabbit" << endl;
    return 0;
}