AtCoder AGC #016 : F - Games on DAG

実装は割とシンプルなんだよな。
http://agc016.contest.atcoder.jp/tasks/agc016_f

問題

DAGであるグラフGが与えられる。
Gの部分グラフG'を考える。

頂点1,2にそれぞれコマがある状態から、2人でターン制のゲームを行う。
自分の手番では、どちらかの駒をその頂点の隣接頂点のいずれかに移動する。
自分の手番でどちらも移動できない場合、負けとなる。

G'の選び方2^|E|通りのうち、先手が勝つのは何通りか。

解法

グラフG'の各頂点vに対してGrundy数A(v)を考える。
先手が勝つのはA(1) xor A(2) != 0、すなわちA(1)!=A(2)の場合となる。

Grundy数Aが決まっているときの辺の条件を考えると以下のようになる。

• 頂点vからは、Grundy数が1～(v-1)の頂点に最低1つずつは辺がある。
• 頂点vからは、Grundy数がvの頂点に辺はない。
• 頂点vからは、Grundy数が(v+1)以上の頂点に辺があってもなくてもよい。

上記の計算は容易であるが、そもそもGrundy数を列挙するのは困難である。
よってbitDPで高速化しよう。

以下を考える。dp(全頂点のbitmask)が求める値である。
dp(mask) := maskの範囲の頂点のGrundy数が確定済みであり、mask以外の範囲の頂点群はmask中の最大Grundy数より大きい場合で、かつA(1)!=A(2)である組み合わせ

bitmask Sに対し、S中最大のGrundyの次のGrundy数を持つ頂点群Tを考える。
UをS,T以外の頂点のbitmaskとすると、以下のようになる。

1. T内の頂点群は互いに辺をもたない。
2. T内の頂点群はUの頂点群に対し任意の辺を持てる
3. U内の頂点群はTのうち最低1点以上に辺をもつ
4. Tに頂点1と2が同時に含まれることはない(A(1)=A(2)となるため)

2つめと3つめの条件の組み合わせを考えつつ、dp(S)からdp(S|T)の値を求めよう。

int N,M;
int E[15];
ll dp[1<<15];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	while(M--) {
		cin>>x>>y;
		x--,y--;
		E[x] |= 1<<y;
	}
	
	dp[0]=1;
	for(int ST=1;ST<1<<N;ST++) {
		int U=((1<<N)-1)^ST;
		for(int S=ST-1; S>=0; S--) {
			S&=ST;
			int T=ST^S;
			if((T&3)==3) continue;
			
			ll mul=1;
			FOR(i,N) {
				if(T&(1<<i)) (mul *= 1<<__builtin_popcount(E[i]&U))%=mo;
				if(U&(1<<i)) (mul *= (1<<__builtin_popcount(E[i]&T))-1)%=mo;
			}
			(dp[ST] += mul*dp[S])%=mo;
		}
	}
	cout<<dp[(1<<N)-1]<<endl;
}

まとめ

このBitDPは思いつかないな…。