TopCoder SRM 640 Div2 Medium NumberGameAgain

一見ややこしいけどコードは短い。
http://community.topcoder.com/stat?c=problem_statement&pm=13557

問題

整数xの初期値を1とする。
xに対し、

• xを２倍する
• xを２倍して1加える

という処理を何度か行う。xが2～(2^K-1)の任意のタイミングでゲームを終了することができる。

ただ、その途中配列table[i]に含まれる数値は経由してはならない。
ゲームを終了できるxは何通りあるか。

解法

table[i]が２進数でp桁とすると、xのうち頭p桁がtable[i]となる数値は到達できないため、その分2^(K-P)を解から引いていく。
table[i]からtable[j]に到達できる場合はtable[j]を考慮する必要はない点に注意。

class NumberGameAgain {
	public:
	long long solve(int k, vector<long long> table) {
		int N=table.size();
		int ng[30]={},msb[30]={},i,j;
		
		sort(table.begin(),table.end());
		FOR(i,N) while(1LL<<(1+msb[i])<=table[i]) msb[i]++;
		FOR(i,N) for(j=i+1;j<N;j++) if((table[j]>>(msb[j]-msb[i]))==table[i]) ng[j]++;
		
		ll ret=(1LL<<k)-2;
		FOR(i,N) if(ng[i]==0) ret -= (1LL<<(k-msb[i]))-1;
		return ret;
	}
}

まとめ

割とあっさり。