Codeforces #260 Div1 B. A Lot of Games

Trieを思いついたのは良かったけど、ちょっとWAした。
http://codeforces.com/contest/455/problem/B

問題

文字列集合が与えられるので、２人でゲームを行う。
このゲームでは空文字列から初めて２人で交互に文字列の末尾に１文字追加する。
この時得られる文字列は、文字列集合中のいずれかの文字列のprefixでなければならない。

条件を満たすような末尾１文字がなければ、そのプレイヤーは負けである。
また、条件を満たすような末尾１文字が存在するなら、そちらに遷移しなければならない(あきらめて負けにすることはできない)

このようなゲームをK回行う。
i回目の敗者が(i+1)回目の勝者となる。
両者最適手を取ると、最後K回目の勝者は先手後手どちらか。

解法

文字列集合からTrieを作り、その上でDFSすることで、先手が以下のいずれの戦略を取れるか判定する。

• 先手は勝ち負けを選択できる
  • この場合、先手は(K-1)回目までわざと負けて毎回先手をキープしつつK回目だけ勝てばよいので先手必勝。
• 先手は必ず勝つ
  • 毎回勝者が入れ替わるので、Kの偶奇で最後の勝者が決まる。
• 先手は必ず負ける
  • 毎回負ける上、毎回先手を取らせられるので先手がK回負け続けるので、後手必勝。

ll N,K;
vector<string> S;

class Trie {
public:
	vector<vector<int> > V;
	int find(string s) {
		int cur=0;
		ITR(it,s) if((cur=V[cur][*it])==0) return -1;
		return cur;
	}
	void create(vector<string> S) {
		V.clear();
		V.push_back(vector<int>(256));
		sort(S.begin(),S.end());
		ITR(it,S) {
			int cur=0;
			ITR(c,(*it)) {
				if(V[cur][*c]==0) V.push_back(vector<int>(256)),V[cur][*c]=V.size()-1;
				cur=V[cur][*c];
			}
		}
	}
};

Trie t;

bool winwin(int cur) {
	int i;
	FOR(i,256) if(t.V[cur][i]!=0) {
		if(winwin(t.V[cur][i])==false) return true;
	}
	return false;
}

bool loselose(int cur) {
	int i,num=0;
	
	FOR(i,256) if(t.V[cur][i]!=0) {
		if(loselose(t.V[cur][i])==false) return true;
		if(loselose(t.V[cur][i])==true) num++;
	}
	if(num) return false;
	return true;
}

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>K;
	FOR(i,N) {
		string s;
		cin>>s;
		S.push_back(s);
	}
	t.create(S);
	bool b1=winwin(0);
	bool b2=loselose(0);
	if(!b1) {
		cout << "Second" << endl;
	}
	else {
		if(b2) {
			cout << "First" << endl;
		}
		else {
			if(K%2) cout << "First" << endl;
			else cout << "Second" << endl;
		}
	}
	
}

まとめ

Trieをライブラリ化しておいてよかった。
先手が狙って負けられるかのDFSの書き方に苦戦して3WAした。