TopCoder SRM 672 Div2 Hard Tdetectived2

問題名「*****Div2」じゃないんだ。
http://community.topcoder.com/stat?c=problem_statement&pm=14076

問題

0～(N-1)番のN人の人がいる。
この中で王女である0番以外の誰かが１人犯人であることが分かっている。

i番の人はj番の人をどの程度怪しいと思っているか、行列S[i][j]で0～9の値で与えられる。
探偵は以下の順でN人に問い合わせを行う。

• 最初は0番固定である。
• 今まで問い合わせた人の意見から、問い合わせてない人のうち怪しさの最大値を求める。
• 前記最大値を持つ人に次問い合わせる。同着の場合、だれかランダムで問い合わせる。

1～(N-1)番の人がそれぞれ犯人であるケースにおいて、最短何人目の問い合わせで犯人に当たるか求めよ。

解法

Nが最大18と小さいので、問い合わせた人をbitmaskで表現し、2^N通り総当たりしながら、問題文の条件通り次に問い合わせを行う可能性のある人を求めていけば良い。

int is[1<<18];

class Tdetectived2 {
	public:
	int reveal(vector <string> s) {
		int val[20];
		int N=s.size();
		int i,j,k;
		
		FOR(i,N) val[i]=100;
		ZERO(is);
		
		is[1]=1;
		for(int mask=0;mask<1<<N;mask++) if(is[mask]) {
			int ma[20]={};
			FOR(i,N) if(mask&(1<<i)) FOR(j,N) ma[j]=max(ma[j],s[i][j]-'0');
			
			int md=-1,ma2=0;
			FOR(i,N) if((mask&(1<<i))==0) {
				if(md<ma[i]) md=ma[i], ma2=0;
				if(md==ma[i]) ma2 |= 1<<i;
			}
			FOR(i,N) if(ma2&(1<<i)) {
				is[mask | (1<<i)] = 1;
				val[i]=min(val[i],__builtin_popcount(mask));
			}
		}
		
		int ret=0;
		FOR(i,N) ret += i*val[i];
		return ret;
	}
}

まとめ

問題設定はえらいややこしいが、Nの大きさからbitdpであることに気づけば後は難しいことはない。