TopCoderOpen 2016 Round2B Medium FoxAndGemstone

これは思いつかんなぁ…。
https://community.topcoder.com/stat?c=problem_statement&pm=14296

問題

N個のバッグがある。
各バッグには、A～Pの計16種類の宝石がそれぞれいくつか入っている。

同じ種類の宝石は同じ重さで、異なる種類の宝石は互いに異なっていることが分かっている。

ここで、宝石を両皿に１個ずつ載せられる天秤量りがあるとする。
これにより、宝石の重さの絶対値はわからないが、宝石の大小関係は判明する。
宝石の重さの大小関係が判明したとき、どのバッグが一番重いか必ず判定することは可能かどうか答えよ。

解法

内容物が同じバッグは取り除こう。
宝石の種類数P=16とする。
条件を満たすには、宝石の重さの大小関係16!通りについて、それぞれどのバッグが一番重いか判定できれば良い。
逆にいうと、各バッグが最も重くなるケースを数え上げ、その和が16!であれば条件を満たす。

各バッグが最も重くなる組み合わせは、bitDPで数え上げることができる。
各バッグが最も重くなる条件は、宝石の重さを重い順に並べたとき、その任意のprefixについて、各バッグそのprefixに含まれる宝石の個数を数えたとき、最も重いバッグ中の宝石が(同着で良いので)最大であることである。
これは各prefixをbitmaskであらわすことで、bitDP出来る。

１点注意点として、bitmaskに対応する宝石の個数は前処理で先に数え上げておこう。
BitDP中に行うと計算量がO(2^P*P*N^2)になりTLEする。

int num[51][16];
int num2[51][1<<16];
ll dp[1<<16];

class FoxAndGemstone {
	public:
	string isPossible(vector <string> B) {
		int i,x,y,mask;
		
		FORR(s,B) sort(s.begin(),s.end());
		sort(B.begin(),B.end());
		B.erase(unique(B.begin(),B.end()),B.end());
		int N=B.size();
		ZERO(num);
		ZERO(num2);
		FOR(i,N) {
			FORR(r,B[i]) num[i][r-'A']++;
			FOR(x,1<<16) FOR(y,16) if(x&(1<<y)) num2[i][x]+=num[i][y];
		}
		
		ll tot=0;
		FOR(x,N) {
			ZERO(dp);
			dp[0]=1;
			
			for(int mask=1;mask<1<<16;mask++) {
				FOR(y,N) if(num2[y][mask]>num2[x][mask]) break;
				if(y<N) continue;
				FOR(y,16) if(mask&(1<<y)) dp[mask] += dp[mask^(1<<y)];
			}
			tot+=dp[(1<<16)-1];
		}
		
		if(tot==16LL*15*14*13*12*11*10*9*8*7*6*5*4*3*2) return "Possible";
		return "Impossible";
		
		
	}
}

まとめ

よくこんな問題考えるなぁ。