Codeforces #197 Div2. C. Xenia and Weights

CF197はDiv2なので練習のみ。
http://codeforces.com/contest/339/problem/C

問題

1～10kgの重りのうち幾つかが無限個ある。
ここで天秤の左右に交互に１個ずつ計M個に達するまで、以下の条件を満たすように重りを乗せて行きたい。

• 重りを１個追加するたび、追加した側の方が重くなる。
• 直前と同じ重さの重りを乗せることはできない。

条件を満たす重りの乗せ方を答えよ。

解法

重りの重さは最大10kgなので、左右の重さの差が9kg以内にしないと次の重りを乗せたときに天秤の傾きを変えられない。
現在の左右の重さの差と、次の手で利用可能な重さのbitmaskを使ってDPすればよい。
重りの種類がN個ならM*N*2^N回のループで処理できる。

string S;
int M;
int dp[1051][11];

void solve() {
	int f,i,j,k,l, x,y;
	
	cin>>S>>M;
	for(y=1;y<=10;y++) if(S[y-1]=='1') dp[0][y]=1<<y;
	
	for(i=1;i<M;i++) {
		for(x=1;x<=10;x++) for(y=1;y<=10;y++) {
			if(S[y-1]=='0') continue;
			if(x>=y) continue;
			if((dp[i-1][x] & ~(1<<y)) == 0) continue;
			dp[i][y-x] |= 1<<y;
		}
	}
	
	int R[1051];
	FOR(x,11) {
		j=0;
		if(dp[M-1][x]) {
			for(y=M-1;y>=0;y--) {
				for(i=1;i<=10;i++) if((y==0 || i!=j) && dp[y][x] & (1<<i)) break;
				R[y]=j=i;
				x=i-x;
			}
			_P("YES\n");
			FOR(i,M) _P("%d ",R[i]);
			_P("\n");
			return;
		}
	}
	_P("NO\n");
}

まとめ

こういう問題は結構好き。
問題にするために無理やり不自然な仮定を置くのはちょっとね。