kmjp's blog

競技プログラミング参加記です

KCPCおめでとうコンテスト : F. string game

こっちの方が迷わなかった。
https://www.hackerrank.com/contests/kcpc-omedetooo/challenges/add-string-game

問題

N個の文字列が与えられた状態で、2人交互にターンが来るゲームを行う。
初期状態で、文字列Sは空文字を持つ。
各自のターンでは1~K文字の間で任意の文字をSの末尾に追加する。
その際、N個の文字列のいずれかのPrefixとSが一致しなければならず、そうでなければ負けとなる。

互いに最適手を取るとき、勝者はいずれか。

解法

元の文字列集合をTrie木にしよう。
各ターンでは、このTrie木において、最初rootにおかれた駒を1~K個分下におろす行為に相当する。
自分のターンで葉にたどり着けば勝ちである。

このように問題を言い換えると、だいぶ扱いやすくなる。
葉から順に、その頂点に駒がある状態でターンが回ってきたとき、勝てるかどうかを求めていこう。
もし勝てない場合、そこから1~K個親の頂点は、逆に勝てることになる。
このフラグ立ては累積和を使うと高速に行える。

int N,K;
vector<string> S;
map<int,int> E[501011];
int P[501011][20],Q[501011];
int M;
int win[501011];

void dfs(int cur,int pre,string& S) {
	P[cur][0]=pre;
	if(S.empty()) return;
	int nex=S.back();
	S.pop_back();
	if(E[cur].count(nex)==0) E[cur][nex]=M++;
	dfs(E[cur][nex],cur,S);
}

void dfs2(int cur,string& S) {
	int i;
	FORR(m,E[cur]) {
		S.push_back(m.first);
		dfs2(m.second,S);
		S.pop_back();
		win[cur]+=win[m.second];
	}
	
	if(win[cur]==0) {
		win[P[cur][0]]++;
		win[Q[cur]]--;
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	M=2;
	S.resize(N);
	FOR(i,N) {
		cin>>S[i];
		reverse(ALL(S[i]));
		dfs(1,0,S[i]);
	}
	FOR(i,18) FOR(x,M) P[x][i+1]=P[P[x][i]][i];
	FOR(x,M) {
		Q[x]=x;
		FOR(i,18) if((K+1)&(1<<i)) Q[x]=P[Q[x]][i];
	}
	
	dfs2(1,s);
	if(win[1]==0) cout<<"tempura"<<endl;
	else cout<<"yamunaku"<<endl;
}

まとめ

ところでKCPCって何ですかね?