AOJ2369CatChecker

2017/11/04

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

問題

CatChecker | Aizu Online Judge

解法

区間 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;
}