Google Code Jam 2018 Round1B : C. Transmutation

これもいい問題。
https://codejam.withgoogle.com/2018/challenges/0000000000007764/dashboard/000000000003675b

問題

M種類の金属がそれぞれC[i]グラムある。

金属iは、金属R(i,0)とR(i,1)の２種類の金属が1グラムずつあるとそれらを消費して1グラム生成できる。
このルールは任意回数実行できるが、整数グラム単位でしか実現できない。

ここから1番目の金属をできるだけ多く生成したい。
最大何グラム生成できるか。

解法

２分探索で解く。
上記bool値を返す関数を考える。F(0,v)がTrueとなる最大のvが解である。
F(i,v) := i番の金属をvグラム生成できるか

現時点でvグラム以上残っているならこれは問題なくTrueである。
そうでないなら、不足分wグラムを別の場所から生成しなければならない。
そのためにはF(R(i,0),w)とF(R(i,1),w)がともに満たされればよい。

…ということでDFSで判定する。
途中再帰により閉路が生じる可能性があるが、その場合は条件を満たせないということになる。

int M;
int R[101][2];
ll G[101];
ll A[101];
ll lp[101];

int dfs(int cur,ll need) {
	if(lp[cur]) return 0;
	
	if(A[cur]>=need) {
		A[cur]-=need;
		return 1;
	}
	
	need-=A[cur];
	A[cur]=0;
	lp[cur]=1;
	
	if(dfs(R[cur][0],need) && dfs(R[cur][1],need)) {
		lp[cur]=0;
		return 1;
	}
	return 0;
	
}


int ok(ll v) {
	int i;
	FOR(i,M) A[i]=G[i];
	ZERO(lp);
	
	return dfs(0,v);
}

void solve(int TC) {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	FOR(i,M) {
		cin>>R[i][0]>>R[i][1];
		R[i][0]--;
		R[i][1]--;
	}
	FOR(i,M) cin>>G[i];
	
	ll ret=0;
	for(int i=40;i>=0;i--) if(ok(ret+(1LL<<i))) ret+=1LL<<i;
	
	_P("Case #%d: %lld\n",TC, ret);
}

まとめ

意外とコードは短いのね。