問題
http://community.topcoder.com/stat?c=problem_statement&pm=8462
有効グラフが存在し、そのノードにコインが２枚以上あれば1枚を消費し、１枚を隣へ移すことができる。
プレイヤーがゲームを行い、ターゲットとなるノードにコインを置くことができれば負けになる。
ターゲットにコインが置かれないような置き方にするとき、置くことのできる最大のコインの数を求める。
解き方
あるノードにおけるコインの数は、そこから到達できる最大の深さによる。
コインの数は最大の１＜＜（最大の深さー現在の深さ）になるので、重複がないように全てのノードについての和を足す。
ただしターゲットに到達しないノードには好きなだけコインが置けるので、そのようなノードが存在する場合はー１を返す。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int used[60],maxdep[60],n;
vector<string> graph;
class CandyGame {
public:
long long dfs(int depth,int x){
used[x]=1;
maxdep[x]=depth;
long long ret=0;
FORE(i,0,n){
if(graph[x][i]=='Y'&&!used[i]){
ret+=dfs(depth+1,i);
maxdep[x]=max(maxdep[x],maxdep[i]);
}
}
if(depth!=0){
ret+=(1LL<<maxdep[x]-depth);
}
return ret>2000000000 ? 2000000001 : ret;
}
int maximumCandy(vector<string> graph_, int target) {
memset(used,0,sizeof(used));
graph=graph_;
n=graph.size();
long long ret=dfs(0,target);
FORE(i,0,n)if(!used[i])return -1;
return ret>2000000000 ? -1 : ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int used[60],maxdep[60],n;
vector<string> graph;
class CandyGame {
public:
long long dfs(int depth,int x){
used[x]=1;
maxdep[x]=depth;
long long ret=0;
FORE(i,0,n){
if(graph[x][i]=='Y'&&!used[i]){
ret+=dfs(depth+1,i);
maxdep[x]=max(maxdep[x],maxdep[i]);
}
}
if(depth!=0){
ret+=(1LL<<maxdep[x]-depth);
}
return ret>2000000000 ? 2000000001 : ret;
}
int maximumCandy(vector<string> graph_, int target) {
memset(used,0,sizeof(used));
graph=graph_;
n=graph.size();
long long ret=dfs(0,target);
FORE(i,0,n)if(!used[i])return -1;
return ret>2000000000 ? -1 : ret;
}
};