SRM 478 500pt: KiwiJuice

TopCoder

問題概要

N(<15)本のビンがあり、キャパシティはC(<49)その中にはA[i]だけのジュースが最初入っている。任意回数だけ、ジュースを他のビンに移し替えることができる。その際、片方が満杯か空になるまで移し替える。各ビンはキャパシティに応じてP[i]円で売れる。利益を最大化する問題。

考えたこと

  • (当時は手も足もでなかった。何か当時O(3^N)とか言ってたような記憶がおぼろげにある)
  • N=15は確かに3^Nのような気もするけど、よく分からんのであまり気にしないようにしよう。
  • しばらく考えて、一度空や満杯になったビンは以降触る必要が無いことに気づいた。
  • これで探索したら案外間に合うんではないだろうか。嘘っぽいな。嘘か。
  • 考えてみたけどまったく案が出なかったので、諦めて他の人の解答見た。
  • ビットDPしてるように見える。あと部分集合全列挙。でも今一よく分からない。
  • Member SRMでEditorialが無かったのでForumの読んでみたらwriter(りんごさん)のコード読めと言われた。
  • 短くて驚く。でも要するに、どの部分集合をまだ売り払って無いか残しておいて、部分集合のうちいくらかを使うことにしたら1本を残して全部空か満杯になる、ということか。確かに…。
  • でも計算量が読めない。各ビットに対して部分集合は2^popcount(bit)だけあるから、自分の直感では計算量2^(2*N)位になってそうな気がする。これで間に合うのか？
  • なるほど、Σ(n,i)*2^i = (1 + 2)^n = 3^nか。二項定理すごい。
  • 計算量の面さえはっきりすれば後は書くだけ。無事通った。

practiceで通ったコード

計算量O(3^N)。

#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 15;

bool visited[1<<MAX_N];
int memo[1<<MAX_N];
int score[1<<MAX_N];

struct KiwiJuice {

	int theProfit(int C, vector <int> bottles, vector <int> prices) {
		const int N = bottles.size();

		//前処理
		for(int bit=0; bit<(1<<N); bit++){
			int sum = 0, n = __builtin_popcount(bit);
			for(int i=0; i<N; i++)if( (bit>>i)&1 ){
				sum += bottles[i];
			}

			score[bit] += (sum / C) * prices[C]; //満杯のボトル
			score[bit] += (n - (sum / C) - (sum % C == 0 ? 0 : 1)) * prices[0]; //空のボトル
			if(sum % C != 0){
				score[bit] += prices[sum%C]; //余ったもののボトル
			}
		}
		return rec((1<<N)-1);
	}

	//ビットが0ならもう固定されている。計上済み
	int rec(int bit){
		//メモ化処理
		if(visited[bit]){
			return memo[bit];
		}
		visited[bit] = true;

		int& ret = memo[bit];
		ret = 0;

		//基底
		if(bit == 0){
			return ret = 0;
		}

		for(int subset = bit; subset > 0; subset = ((subset - 1) & bit)){
			ret = max(ret, rec(bit & (~subset)) + score[subset]);
		}

		return ret;
	}

};