Introduction to Programming Introduction to Algorithms and Data Structures Library of Data Structures Library of Graph Algorithms Library of Computational Geometry Library of Dynamic Programming Library of Number Theory
区間 がねこ鳴き声か探索する．区間の端が ， で真ん中の で区切ってみる．メモ化しないとTLEした．逆からやると一意に決まる系かと思ったけどそんなことなかった．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
string s ;
int memo [ 505 ][ 505 ];
bool dfs ( int l , int r ) {
if ( l > r ) return true ;
if ( memo [ l ][ r ] != - 1 ) return memo [ l ][ r ];
if ( s [ l ] == 'm' && s [ r ] == 'w' ) {
REP ( i , l + 1 , r ) {
if ( s [ i ] == 'e' ) {
if ( dfs ( l + 1 , i - 1 ) && dfs ( i + 1 , r - 1 )) {
return memo [ l ][ r ] = true ;
}
}
}
}
return memo [ l ][ r ] = false ;
}
int main () {
cin >> s ;
memset ( memo , - 1 , sizeof ( memo ));
if ( dfs ( 0 , s . size () - 1 )) {
cout << "Cat" << endl ;
} else {
cout << "Rabbit" << endl ;
}
return 0 ;
}