B. The Killer Word

2011-05-21

18:13 |

文字列 N 個からなる辞書からこっちが1個えらんで、Sean がそれを当てるゲーム。
最初、えらんだ文字列はすべて伏せてある。文字数はわかる。
Sean は文字(a-z)をguessする。guessした文字が文字列にあったらそれをオープンにする。なかったら 1pt 減点。
Sean のアルゴリズムは、文字の優先順位が与えられるので、その順かつ現時点で有効な選択肢に１つでも含まれる文字ならguessするというもの。
その際、そもそも伏せられた文字数から答えが１つに絞れる場合はguessしないで終了するなど、Seanは賢くやるとする。
文字の優先順位が M 個与えられるので、それぞれについて、Sean の減点が一番多くなるような文字列を求める。

とりあえずシミュレーションしてみる。
Small 通ったので Large やるが計算が終わらない。
Large は N <= 10000, M <= 100 で、コードを見るとなにやらループの入れ子が結構深くて M, N, Nのループになってる。
１つ１つ Sean の減点を求めて最大のものを出すとかいって、なんか重複して計算してるものが多そうだから DP みたいなことをやるんだろうけど思いつかず。

解説を見てると、文字数でクラス分けして、さらに1文字guessするごとにオープンされた文字の位置によってさらにクラス分けして、選択肢が1個になるまでシミュレートしていくとよいと書いてある。なるほど.....
今までいろんな問題を見てきて、「なんとかが最大になるようななんとかを求めよ」みたいなときは DP 感がするようになったのでこれをもっと推し進めたく。

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int N, M;
		cin>>N>>M;
		string D[N];
		string L[M];
		REP(i, N) cin>>D[i];
		REP(i, M) cin>>L[i];
		//REP(i, N) cout<<D[i]<<endl;
		//REP(i, M) cout<<L[i]<<endl;
		
		cout<<"Case #"<<t+1<<":";
		REP(Li, M)
		{
			int lose[N];
			CLR(lose);
			REP(di, N)
			{
				// choose D[di]
				//cout<<"choose "<<D[di]<<endl;
				int ng[N];
				int nng=0;
				CLR(ng);
				REP(i, N)
				{
					if(D[di].SZ != D[i].SZ) {ng[i]=1;nng++;}
				}
				if(nng==N-1) continue;
				
				// begin guess
				REP(li, 26)
				{
					int contains=0;
					REP(i, N)
					{
						if(ng[i]) continue;
						if(D[i].find(L[Li][li])!=D[i].npos) { contains=1; break; }
					}
					if(contains)
					{
						char guess = L[Li][li];
						//cout<<"guess "<<guess<<endl;
						int revealed=0;
						REP(p, D[di].SZ)
						{
							if(D[di][p]==guess) {revealed=1;break;}
						}
						if(!revealed) lose[di]++;
						REP(i, N)
						{
							if(ng[i]) continue;
							REP(p, D[i].SZ)
							{
								if(D[di][p]==guess && D[i][p]!=guess || D[di][p]!=guess && D[i][p]==guess) {ng[i]=1;nng++;break;}
							}
						}
						if(nng==N-1) break;
					}
				}
			}
			int max = -1;
			int maxi = -1;
			REP(i, N)
			{
				//cout<<lose[i]<<endl;
				if(max<lose[i]) {max=lose[i];maxi=i;}
			}
			cout<<" "<<D[maxi];
		}
		cout<<endl;
	}
	return 0;
}