AtCoder ARC #096 : F - Sweet Alchemy

忘れたころにブログ書くのしんどいけど、復習と思って頑張ろう。
https://beta.atcoder.jp/contests/arc096/tasks/arc096_d

問題

N個のドーナツがあり、i番のドーナツを作るのにM[i]のお菓子のもとが要る。
また、1番以外のドーナツについては、P[i]番のドーナツ数により作る数が規定される。
i番のドーナツをC[i]個作る場合、1番以外のドーナツはC[P[i]]≦C[i]≦C[P[i]]+Dの範囲で作らなければならない。

お菓子のもとがXあるとき、最大何個のドーナツを作れるか。

解法

P[i]によって定められる根付き木を考えると、子頂点は親頂点より0≦d[i]≦D個だけ多くのドーナツを作らなければならない。
よって、親側のドーナツを1個作るということはSubTree内のドーナツを1個追加しなければいけないことににある。

言い換えると、SubTree内のM[i]の和だけお菓子のもとを消費すれば、SubTreeの頂点分のドーナツを作れる。
ここから、各頂点について基本的には上記(ドーナツ数/お菓子のもとの和)が大きい順にソートしてドーナツを作ればよい。

基本的には貪欲にベストなものを選んでいけばよいが、ナップサック問題の要領でそうはうまくいかない可能性もある。
ここで、この問題ではドーナツ数を価値、お菓子のもとをコストを考えると、各アイテムの価値は高々Nである。
よって最初にN*3個程度までの価値の範囲でとり方をDP総当たりし、あとは各ケースにおいてコストパフォーマンスの良い順で貪欲に取るようにするとよい。

int N;
ll X,D;
ll M[1010];
int P[1010];
vector<int> E[51];

int Y[1010];
ll Z[1010];
int C[51];

ll cost[51][51*51*51+100];
int from[51][51*51*51+100];

bool cmp(int L,int R) {
	return Y[L]*M[R]>Y[R]*M[L];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>D;
	FOR(i,N) {
		cin>>M[i];
		if(i) {
			cin>>P[i];
			P[i]--;
			E[P[i]].push_back(i);
			Z[i]=D;
		}
		else {
			Z[i]=1<<30;
		}
		C[i]=i;
	}
	
	for(i=N-1;i>=0;i--) {
		Y[i]=1;
		FORR(e,E[i]) {
			Y[i]+=Y[e];
			M[i]+=M[e];
		}
	}
	
	sort(C,C+N,cmp);
	
	FOR(i,N+1) FOR(x,51*51*51+1) cost[i][x]=1LL<<60;
	cost[0][0]=0;
	FOR(i,N) {
		FOR(x,50*50*50+1) {
			for(y=0;y<=min(50,(int)Z[i])&&x+y*Y[i]<=50*50*50;y++) {
				if(cost[i+1][x+y*Y[i]] > cost[i][x]+y*M[i]) {
					cost[i+1][x+y*Y[i]]=cost[i][x]+y*M[i];
					from[i+1][x+y*Y[i]]=y;
				}
			}
		}
	}
	
	ll ma=0;
	FOR(x,50*50*50+1) if(cost[N][x]<1LL<<60) {
		int cnt[51];
		int cur=N;
		y=x;
		while(cur) {
			cnt[cur-1]=Z[cur-1]-from[cur][y];
			y-=from[cur][y]*Y[cur-1];
			cur--;
		}
		
		ll ret=x;
		ll left=X-cost[N][x];
		if(left<0) continue;
		FOR(i,N) {
			ll del=min((ll)(Z[C[i]]-min(50LL,Z[C[i]])),left/M[C[i]]);
			ret+=del*Y[C[i]];
			left-=del*M[C[i]];
		}
		ma=max(ma,ret);
	}
	
	cout<<ma<<endl;
	
	
	
	
}

まとめ

これ本番でさっくり思いつける気がしない。