Codeforces ECR #037 : D. Tanks

何気に手こずった問題。
http://codeforces.com/contest/920/problem/D

問題

N個の入れ物があり、初期状態で体積A[i]の水が入っている。
1回でKの体積の水をすくえるスコップで、これらの水を入れ物間で移すことを考える。
スコップには、Kもしくは入れ物内の水のすべてのうち小さい体積分をすくい、即座に別の入れ物に入れることができる。

スコップを使い水の体積がVとなる入れ物を作れるか。
可能ならその手順を示せ。

解法

まずA[i]の総和がV以上であることは前提である。
あとはどこかに容量d ≡ V (mod K)となる入れ物を作れれば、d＞Vなら余分な水をくみ出せばいいし、d＜Vなら他の水を別の場所に集めてそこからKずつ組み入れればよい。
よってO(NK)のDPでmod K毎にそのような状態を生成できる入れ物の集合を求めればよい。

int N,K,V;
vector<int> dp[5050];
int A[5050];
int S;
int did[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>V;
	
	dp[0].push_back(0);
	for(i=1;i<=N;i++) {
		cin>>A[i];
		S+=A[i];
		FOR(j,K) if(dp[j].size() && dp[(j+A[i])%K].empty()) {
			if(dp[j].back()!=i) {
				dp[(j+A[i])%K]=dp[j];
				dp[(j+A[i])%K].push_back(i);
			}
		}
	}
	if(S>=V && ((S-V)%K==0 || V%K==0)) {
		vector<vector<int>> LV;
		for(i=2;i<=N;i++) {
			int movs=(A[i]+K-1)/K;
			if(movs) LV.push_back({movs,i,1});
		}
		if(V%K==0) {
			if(V) LV.push_back({V/K,1,2});
		}
		else {
			if((S-V)/K) LV.push_back({(S-V)/K,1,2});
		}
		_P("YES\n");
		FORR(v,LV) _P("%d %d %d\n",v[0],v[1],v[2]);
		return;
	}
	
	
	if(S<V || dp[V%K].empty()) return _P("NO\n");
	_P("YES\n");
	
	int S2=0;
	if(dp[V%K].size()>=2) {
		S2=A[dp[V%K][1]];
		did[dp[V%K][1]]=1;
		for(i=2;i<dp[V%K].size();i++) {
			x=A[dp[V%K][i]];
			S2+=x;
			if((x+K-1)/K>0) _P("%d %d %d\n",(x+K-1)/K,dp[V%K][i],dp[V%K][1]);
			did[dp[V%K][i]]=1;
		}
	}
	int first=-1;
	for(i=1;i<=N;i++) if(did[i]==0) {
		if(first==-1) {
			first=i;
		}
		else {
			if((A[i]+K-1)/K>0) _P("%d %d %d\n",(A[i]+K-1)/K,i,first);
		}
	}
	
	if(S2<V) {
		_P("%d %d %d\n",(V-S2)/K,first,dp[V%K][1]);
	}
	else if(S2>V) {
		_P("%d %d %d\n",(S2-V)/K,dp[V%K][1],first);
		
	}
	
}

まとめ

シンプルそうに見えて意外に手こずる問題。