Codeforces #213 Div1. B. Free Market

本番悩んだけど解説見たらあっさり解決。
http://codeforces.com/contest/364/problem/B

問題

N個の品物があり、それぞれの価値C[i]が与えられる。各品物は１つずつしかない。
また、数値Dが与えられる。

初期状態でプレイヤーは１つも品物を持っていない。
プレイヤーは自分の所持する品物の集合Aと、持っていない品物の集合Bに対し、(Aの価値の合計)+D>=(Bの価値の合計)ならAとBを交換できる。

プレイヤーが所持できる品物の価値の合計を最大化せよ。
また、必要な交換回数を最小化せよ。

解法

本番「一旦AとBを交換してAを手放したら、またAを取り戻したいのだけどすでに所有しているB中の品物を一旦放出しないとAと取り戻せなくない…？」とか迷って答えが出なかった。

実は問題文を素直に読むと、交換の際AとBが同じ品物を含んでいてはならないとあるが、実際はAとBが同じ品物を含んでいても良い。
たとえばAとBの共通部分をCとすると、(Aの価値)+D>=(Bの価値)なら(Aの価値)-(Cの価値)+D>=(Bの価値)-(Cの価値)なので、結局AとBの差額がD以下なら、両者からCを除いたものも差額がD以下なので、C以外を交換することができる。

ここまでくればあとは簡単。
(Aの価値の合計)+D>=(Bの価値の合計)の式に対してAとBの内容に制限がなくなった。
よって、まずDPで各品物の部分集合の価値を全パターン列挙する。
次に、自分の所持する総価値0から初めて、自分の価値+D以内にある最大の価値に遷移していけばよい。
自分の価値+D以内に遷移できるポイントがなくなったら終了。

int N,D;
int C[100];
int DP[500020];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>D;
	FOR(i,N) cin>>C[i];
	
	DP[0]=1;
	FOR(i,N) for(x=500000-C[i];x>=0;x--) DP[x+C[i]] |= DP[x];
	
	x=y=0;
	while(1) {
		j=0;
		for(j=0,i=1;i<=D&&(x+i)<=500000;i++) if(DP[x+i]) j=i;
		if(j==0) break;
		x+=j;
		y++;
	}
	_P("%d %d\n",x,y);
}

まとめ

交換の際共通部分があってもよい、と気づけなかったのが痛い。