Codeforces #171 Div2. D. The Minimum Number of Variables

さてD。
http://codeforces.com/contest/279/problem/D

問題

N個の要素からなる数列Aが与えられる。
ここで、M個の要素からなる数列Bを考える。
初期値はB[1]=A[1]で、B[2]～B[M]=0とする。
Bの要素から３つの要素i,j,yを選び(重複可)、B[y]=B[i]+B[j]という演算をN-1回繰り返し、その都度B[y]がA[2]、A[3]…A[N]と一致するようにしたい。

このとき最小のMを答えよ。

解法

ビットDPで解決可能。
ビットマスクKのうちビットの立った位置に対応するAの要素が、現在Bに格納されているとする。
そのようなKが実現可能かどうかDPで処理していく。

ここでK中でビットの立っているAの要素２つの和で、KのMSBより１つ上のビットに対応するAの要素を作れるか調べる。

作れる場合、MSBの１つ上のビットを立てたKも実現可能。(この場合、ビット数が一つ増える＝必要なBの要素数が1つ増える)
さらに、元の２要素のビットの片方を落としたKも実現可能。(この場合、ビット数が固定で、元の２要素のうち片方を上書きする）

最終的にNビット目が立ったKのうち、最もビット数が少ないものが答え。

int N,M;
int A[100];
vector<pair<int, int> > P[30];
int dp[1<<24];

void solve() {
	int f,r,i,j,k,l,x,y;
	int ma=0;
	
	N=GETi();
	FOR(i,N) A[i]=GETi();
	
	if(N==1) {
		_P("1\n");
		return;
	}
	
	FOR(i,N) {
		FOR(j,i) if(A[j]==A[i]) P[i].push_back(make_pair(j,-1));
		FOR(j,i) for(k=j;k<i;k++) {
			if(A[j]+A[k]==A[i]) P[i].push_back(make_pair(j,k));
		}
	}
	
	ZERO(dp);
	dp[1]=1;
	int msb=0;
	for(i=1;i<N;i++) {
		for(k=1<<(i-1);k<(1<<i);k++) {
			if(dp[k]==0) continue;
			FOR(j,P[i].size()) {
				pair<int,int> p = P[i][j];
				
				if((k & (1<<p.first)) == 0) continue;
				if(p.second>= 0 && (k & (1<<p.second)) == 0) continue;
				dp[(k | (1<<i))] = 1;
				FOR(l,i) if(k & (1<<l)) dp[(k | (1<<i)) ^ (1<<l)] = 1;
			}
		}
	}
	
	int mbc=99;
	for(k=1<<(N-1);k<1<<N;k++) {
		if(dp[k]==1) mbc=min(mbc,__builtin_popcount(k));
	}
	
	if(mbc==99) mbc=-1;
	_P("%d\n",mbc);
	
	return;
}

まとめ

N<=23の時点でビットDPと推測できるね。