知らん知識だ…。
https://atcoder.jp/contests/abc229/tasks/abc229_h
問題
N*Nのグリッドがあり、いくつかのセルには白い駒や黒い駒がある。
これを用いて2人でターン制のゲームを行う。
各自のターンでは以下のいずれかを行う。自分の手番で行える手がなくなると負けである。
- 先手：
- 白い駒の上のマスが空いていたら、そこに駒を移動する
- 黒い駒を1つ選んで取り除く
- 後手：
- 黒い駒の上のマスが空いていたら、そこに駒を移動する
- 白い駒を1つ選んで取り除く
解法
Editorial読んでること前提で書いていく。
ある列の状態sの評価値をf(s)とする。
各列の状態における評価値の合計が正なら先手が勝利、0以下なが後手が勝利となるように評価値を定める。
1つの列に着目すると、状態は3^N通りある。
それぞれの評価値を考える。
3^N個の状態に対応する3^N個の頂点を持つ有向グラフを考える。
先手の操作で遷移可能な辺を白い有向辺、後手の操作で遷移可能な辺を黒い有向辺で結ぶと、このグラフはDAGとなる。
そこで、遷移先の状態の評価値が確定した点から、その状態の評価値を定めよう。
その際、以下のように評価値を設定したい。
- 白辺で遷移したら評価値が下がるようにしたい。そのため、今いる点の評価値は、白辺の遷移先の最大値より大きい
- 黒辺で遷移したら評価値が下がるようにしたい。そのため、今いる点の評価値は、黒辺の遷移先の最小値より小さい
今評価値を定めたい状態sに対し、前者の最大値をX、後者の最小値をYとすると、X＜f(s)＜Yとなるようにしたい。
その際、以下のように値を定めると、必ずX＜Yとなる。
- f(s) = p/(2^q)と 有理数で定めることを考える。qを0からインクリメントしていき、X＜f(s)＜Yとなるf(s)が取れるまでqを大きくしていく。
- qが定まったら、pは絶対値が最小値なるものを取る。
実際には、問題の条件ではqは6程度にしかならないため、評価値を固定小数点で扱うと楽である。
int N; string S[8]; int p3[9]; vector<int> EA[9*9*9*9],EB[9*9*9*9],R[9*9*9*9]; int in[9*9*9*9]; ll G[9*9*9*9]; void solve() { int i,j,k,l,r,x,y; string s; p3[0]=1; FOR(i,8) p3[i+1]=p3[i]*3; int mask; queue<int> Q; FOR(mask,p3[8]) { int T[8]; FOR(i,8) T[i]=mask/p3[i]%3; FOR(i,8) { if(T[i]==1) { EB[mask].push_back(mask-p3[i]); R[mask-p3[i]].push_back(mask); in[mask]++; if(i&&T[i-1]==0) { EA[mask].push_back(mask-p3[i]+p3[i-1]); R[mask-p3[i]+p3[i-1]].push_back(mask); in[mask]++; } } if(T[i]==2) { EA[mask].push_back(mask-2*p3[i]); R[mask-2*p3[i]].push_back(mask); in[mask]++; if(i&&T[i-1]==0) { EB[mask].push_back(mask-2*p3[i]+2*p3[i-1]); R[mask-2*p3[i]+2*p3[i-1]].push_back(mask); in[mask]++; } } } if(in[mask]==0) Q.push(mask); } while(Q.size()) { int cur=Q.front(); Q.pop(); ll X=-1<<30,Y=1<<30; FORR(a,EA[cur]) X=max(X,G[a]); FORR(a,EB[cur]) Y=min(Y,G[a]); for(i=16;i>=0;i--) { int d=1<<i; ll XC=X/d*d-d; ll YC=Y/d*d+d; while(XC<=X) XC+=d; while(YC>=Y) YC-=d; if(XC>YC) continue; if(XC<=0&&YC>=0) { G[cur]=0; } else if(YC<=0) G[cur]=YC; else G[cur]=XC; break; } FORR(a,R[cur]) { in[a]--; if(in[a]==0) Q.push(a); } } cin>>N; ll sum=0; FOR(y,N) cin>>S[y]; FOR(x,N) { mask=0; for(y=N-1;y>=0;y--) { mask*=3; if(S[y][x]=='W') mask++; if(S[y][x]=='B') mask+=2; } sum+=G[mask]; } if(sum>0) cout<<"Takahashi"<<endl; else cout<<"Snuke"<<endl; }
まとめ
知らない知識なのでこれは解けなくてもしょうがないな…。
