こっちの方が迷わなかった。
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って何ですかね?