TopCoder SRM 757 Div1 Medium MatchNim

ResubmitでTLEを回避したのはよかったけども。
https://community.topcoder.com/stat?c=problem_statement&pm=15441

問題

以下の変形Nimを考える。
石の代わりにマッチ棒の山を使うNimを行う。
自分の手番では、通常のNim通り1つの山を選択しいくつかマッチ棒を取り除く。
その後、取り除いたマッチ棒の分、山を選択してその山のマッチ棒を全焼させることができる。
（取り除いたマッチ棒を使い切らなくてもよい）

山の状態が与えられたとき、先手後手どちらが必勝か。

解法

基本的には状態を列挙して全探索。
適度に枝刈りしないと間に合わない。
例えば以下の工夫がある。

• (山の数-1)より多いマッチ棒の山があれば、全部の山を燃やせるので必勝。
• 同じマッチ棒の数を持つ山が複数ある場合、うち1つだけを試す。
• マッチ棒の数は常にソートし、状態を減らす
• 操作後のマッチ棒の状態を何度も作り直さないよう、ループ順を工夫する

以下の解で最悪ケース1.7s程度。

string S[2]={"Zara","Yvonne"};
map<vector<int>,bool> memo;
class MatchNim {
	public:
	bool win(vector <int> P) {
		sort(ALL(P));
		if(memo.count(P)) return memo[P];
		if(P.empty()) return false;
		
		int N=P.size();
		if(P.back()>=N-1) return memo[P]=true;
		
		int i,j,k;
		int did[10]={};
		FOR(i,N) {
			if(did[P[i]]) continue;
			did[P[i]]=1;
			int mask;
			FOR(mask,1<<N) if((mask&(1<<i))==0 && __builtin_popcount(mask)<=P[i]) {
				vector<int> nex;
				FOR(k,N) {
					if(k!=i&&(mask&(1<<k))==0) {
						nex.push_back(P[k]);
					}
				}
				int tot=__builtin_popcount(mask);
				for(k=max(1,tot);k<=P[i];k++) {
					if(k<P[i]) nex.push_back(P[i]-k);
					
					if(win(nex)==0) return memo[P]=1;
					if(k<P[i]) nex.pop_back();
					
				}
			}
		}
		
		return memo[P]=0;
		
	}
	
	string whoWins(vector <int> P) {
		return S[win(P)];
	}
}

まとめ

うーん。
これ本質はなんなんだ。全探索の枝刈りが想定解？