SRM672 Div2 Hard - Tdetectived2

・問題
https://community.topcoder.com/stat?c=problem_statement&pm=14076
なんかレイアウトが崩れている気がするが...(2015/11/4 Chromeで見た)直ってた(2015/11/6)
めっちゃ文章長くて問題の把握に時間かかった。そこも含めて慣れていきたい。

・概要
n人のグループがあり、0~n-1までナンバリングされている。0番は目撃者で、1~n-1番のうち1人だけkillerがいる。探偵はkillerを見つけ出したい。
探偵はその人と話せばその人がkillerであるか否かがわかる。探偵は0~n-1番の人に対してそれぞれギワク度(0~9)をもっている。数字が高いほどギワク度が高い。はじめはギワク度は全員0である。調査を開始するにあたって0番は(killerではないので)0番にインタビューする。
ここで、n人のグループはi番とj番の仲の悪さをs[i][j]で与える。仲が悪いと疑わしい発言をするので、探偵がi番にインタビューするとj番のギワク度がs[i][j]まであがる(もともとそれより大きかったら変化はない)。
探偵はインタビューする人を
　まだインタビューをまだしていない人の中で、
　その時点でのギワク度が最も高く、
　最も高い人が複数いる場合はそのいずれか
から選ぶ。
k番をインタビューするために必要な最小の回数をans[k]とした時の
1*ans[1]+2*ans[2]+...+(n-1)*ans[n-1]
の値を求めよ。

・アイデア
インタビューをする人を決めるとき、候補が複数いる場合はどうしよう、と思ってとりあえず例1や2を紙にかいてシミュレーションしてみる。なかなかムズい。。。
でもこれは「状態遷移」ってことだなってことに15分ぐらいして気づく。そしてこの探索の仕方は幅優先探索だ！ってことに気づければあとはやるだけの全探索問題になっておしまい。
ちなみに探索済みを'/'で表すことにしたのは、ASCIIで'/'は'0'の１つ手前にあったから。'/'-'0'=-1になって、最大値を更新してしまうことがないように。

・実装(C++)

int reveal(vector <string> s) {
	int ans[18]={0};
	int n=s.size();
	fill(ans,ans+n,100);

	//BFS
	queue<string> que;
	string start=s[0];
	start[0]='/'; //0番に対するインタビューは終了した
	que.push(start);
	while(!que.empty()){
		string v=que.front(); que.pop();

		//そこまでにインタビューした人数
		int turn=0;
		for(int i=0; i<v.size(); ++i){
			if(v[i]=='/') turn++;
		}
		//cout << v + " turn=" << turn << endl;

		//現時点でのsuspicion levelの最大値
		int sus=0;
		for(int i=0; i<n; ++i){
			sus=max(sus,v[i]-'0');
		}

		for(int i=0; i<n; ++i){
			if(v[i]-'0' == sus){ //i番にインタビュー
				ans[i]=min(ans[i],turn);

				string tmp=v;
				tmp[i]='/';
				//suspicion levelの更新
				for(int j=0; j<n; ++j){
					if(tmp[j]=='/') continue;
					tmp[j] = max(s[i][j]-'0', tmp[j]-'0')+'0';
				}
				que.push(tmp);

				//printf("pushed :: %d\n", i);
			}
		}
	}

	int ret=0;
	for(int i=1; i<n; ++i) ret+=i*ans[i];
	return ret;
}