SRM 666 div2

Easy

問題文

省略

解法

シミュレーション
boolの関数visitedを利用し、既に訪れたところに再び来た場合は、"Lose", -1に到達した場合は、"Win"とする.

コード

class DevuAndGame {
public:
    string canWin(vector <int> nextLevel) {
	int now = 0;
	vector<bool> visited(nextLevel.size(),false);
	visited[0] = true;
	while(true){
	    now = nextLevel[now];
	    if(now == -1) return "Win";
	    if(visited[now]) break;
	    visited[now] = true;
	}
	return "Lose";
    }
}

Med

問題文

省略

解法

枝刈り全探索(メモ化再帰)
最後の状態から連続する"ab"という文字列があれば消していく.
これを繰り返す.
この際、既に訪れた文字列に対する結果をmapにつめておく.

かなり効率が悪い…

※ 他の人の解法を見たらもっと良いやり方でやっていた.
'a'という文字を+1, 'b'という文字を-1とし、文字列の最初から加算していく.
そして、途中で負数になった場合は"Bad"で最終的に0になったら"Good"となる.
この方法だと文字列の長さをNとすると、O(N)でできる.

スタック等のデータ構造を使ってもできる.

コード

class GoodString {
public:
    map<string,bool> visited;
    bool rec(string s){
	if(s.empty()) return true;
	if(visited.count(s)){
	    return visited[s];
	}
	int len = s.size();
	bool res = false;
	for(int i = 0 ; i < len-1 ; i++){
	    if(s[i] == 'a' && s[i+1] == 'b'){
		string t = s.substr(0,i)+s.substr(i+2);
		res |= rec(t);
	    }
	}
	return visited[s] = res;
    }
    
    string isGood(string s) {
	int size = s.size();
	if(size&1) return "Bad";
	return (rec(s) ? "Good" : "Bad");
    }
}

Hard

問題文

省略

解法

木DP
dp[頂点][残りの移動回数][その頂点に戻るか戻らないか] := 最大の得点

POJの2486と制約が少し異なるだけで全く同じ問題(配列等のサイズを変えたらACした).

コード

typedef vector<int> Vec;

int dp[110][110][2];
Vec G[110];

class CollectingTokens {
public:
    void dfs(int v,int prev,Vec &T,int L){
	dp[v][0][0] = dp[v][0][1] = T[v];
	for(int i = 0 ; i < (int)G[v].size() ; i++){
	    int next = G[v][i];
	    if(next == prev) continue;
	    dfs(next,v,T,L);
	    for(int j = L ; j >= 0 ; j--){
		for(int k = 0 ; k <= L ; k++){
		    if(j+k+2 <= L){
			dp[v][j+k+2][0] = max(dp[v][j+k+2][0],dp[next][k][0]+dp[v][j][0]);
			dp[v][j+k+2][1] = max(dp[v][j+k+2][1],dp[next][k][0]+dp[v][j][1]);
		    }
		    if(j+k+1 <= L)
			dp[v][j+k+1][1] = max(dp[v][j+k+1][1],dp[next][k][1]+dp[v][j][0]);
		}
	    }
	}
    } 
    
    void init(){
	memset(dp,-1,sizeof(dp));
	for(int i = 0 ; i < 110 ; i++) G[i].clear();
    }
    
    int maxTokens(Vec A, Vec B, Vec tokens, int L) {
	init();
	for(int i = 0 ; i < (int)A.size() ; i++){
	    A[i]--; B[i]--;
	    G[A[i]].push_back(B[i]);
	    G[B[i]].push_back(A[i]);
	}
	dfs(0,-1,tokens,L);
	int res = 0;
	for(int i = 0 ; i <= L ; i++){
	    res = max(res,dp[0][i][1]);
	}
	return res;
    }
}