CSAcademy Round #16 : F. Letter by Letter

これは割と正統派な問題。
https://csacademy.com/contest/round-16/#task/letter-by-letter

問題

N個のK文字の単語が与えられる。
そのうち１つが特別な単語であり、これを当てたい。

単語を先頭から１文字ずつ当てていくことを考える。
プログラム側が１文字の文字を出力して問い合わせると、特別な単語の次の文字がそれと一致するかどうかを返す。
一致する場合、次の出力では次の文字を当てることになる。

問い合わせの応答は、できるだけ特別な単語を当てるまでのクエリ回数が最長となるようになされる。
その範囲で最小回数の問い合わせで単語を当てよ。

解法

単語群をソートし、Trieを構築する。
頂点vの先に特別な単語がある場合、当てるまでの最短問い合わせ回数f(v)をDPで計算する。

f(v)を葉から順に計算していくことを考える。
vの子頂点について、その先の問い合わせ回数が多い順に問い合わせるようにしていけば、問い合わせ回数の最悪回数を抑えることができる。
v'(x)をvの子頂点v'のうち、f(v')が大きい順に並べたときの先頭からx番目の頂点とする。
その時f(v) = max(x+v'(x))となる。

これで問い合わせ順が確定するので、あとはクエリの応答に合わせてTrieを根から順に移動していけばよい。

int N,K;
string S[101010];
map<pair<int,int>,vector<pair<int,pair<int,int>>>> M[101010];

int dfs(int pos,int L,int R) {
	vector<pair<int,pair<int,int>>> V;
	
	if(pos==K) return 0;
	
	for(int x=L;x<R;) {
		int LL=x;
		while(LL<R && S[LL][pos]==S[x][pos]) LL++;
		V.push_back({dfs(pos+1,x,LL),{x,LL}});
		x=LL;
	}
	
	sort(ALL(V));
	reverse(ALL(V));
	int ma=1,i;
	FOR(i,V.size()) ma=max(ma,V[i].first+i+1);
	
	M[pos][{L,R}]=V;
	return ma+1;
}

void dfs2(int pos,int L,int R) {
	if(pos==K) exit(0);
	
	auto V=M[pos][{L,R}];
	int x;
	FORR(v,V) {
		cout<<S[v.second.first][pos]<<endl;
		cin>>x;
		if(x) dfs2(pos+1,v.second.first,v.second.second);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>S[i];
	sort(S,S+N);
	
	dfs(0,0,N);
	dfs2(0,0,N);
}

まとめ

これはあまり迷わなかった。