题解 [ABC229H] Advance or Eat（不平等博弈）
这是一个不平等博弈问题。
不平等，顾名思义，两个人的可执行操作并不相同。在此问题中，尽管两人都可以看到当前局面，但是先手 Takahashi 君只可以移白棋或吃黑棋，而 Snuke 君只可以移黑棋或吃白棋。话说这里的吃棋不是用其它棋子吃而是凭空吃掉，这两个人胃口真好。
解决不平等博弈问题有专门的做法，更深入一些还牵扯理论层面的超现实数。本篇题解不作延伸。
以下是较通用的做法，适用于 DAG：（注，以下先、后手表述均分别指代 Takahashi 和 Snuke）
\color{red}一 思考 & 定义
- 我们发现由于每个人的可执行操作不同，存在这样的性质：无论是先手还是后手，操作一次一定离自己操作不了的局面更近了。这样我们就明白要定义什么了。
- 定义
f_{sta} 代表sta 局面下的评估值。 - 我们希望评估值的性质：假设
u 局面操作一次转移到v 局面，若u 状态先手预期未来能比v 状态移动更多步，那么f_u > f_v ，若u 状态后手预期未来能比v 状态移动更多步，那么f_u < f_v 。即评估值越大，局面对先手越有利，评估值越小，局面对后手越有利。如果有这样的性质，先手走一步，评估值一定会减小，后手走一步，评估值一定会增大（因为自己离失败更进了一步，局面变得更有利于对手）。
\color{red}二 求出 f
- 对于
f_u ，假设先手决策后到达的状态集合是A ，那么f_u> f_v ,\forall v\in A ，后手决策后到达的状态集合是B ，那么f_u< f_v ,\forall v\in B 。我们因此可以求出一个max_u=\max A 和min_u=\min B ，要求f_u 满足max_u<f_u<min_u 。 抽象的来了，我们的f 还要满足两个限制，前一个限制优先：-
- 如果不存在满足条件的
f ，或者当前状态能转移到的点存在未定义，那么当前状态的f 就是未定义。
例子
如果限制
如果限制
如果限制
注：以上过程与超现实数高度相关，建议感兴趣的读者查阅相关资料。
确定胜者的方式：
每个子游戏起始状态的
上述做法的证明见后。
\color{red}三 考虑此题
由于此题列与列之间互不影响，我们可以将该问题的每列划分成一个子游戏。
每个子游戏，按照
map<string,double>f;
double dp(string t)
{
if(f.count(t))return f[t];
double l=-inf,r=inf;
for(int i=0;i<t.size();i++)
{
if(t[i]=='B')
{
string NXT=t;
NXT[i]='.';
l=max(l,dp(NXT));
if(i+1<t.size()&&t[i+1]=='.')
{
NXT[i+1]=t[i];
r=min(r,dp(NXT));
}
}
if(t[i]=='W')
{
string NXT=t;
NXT[i]='.';
r=min(r,dp(NXT));
if(i+1<t.size()&&t[i+1]=='.')
{
NXT[i+1]=t[i];
l=max(l,dp(NXT));
}
}
}
if(l<0&&r>0)return f[t]=0;
int d=1;
if(l<0){d=-1;l=-l,r=-r;swap(l,r);}
for(int i=0;i<=30;i++)
{
int sum=1e12;
double chu=(1<<i);
for(int j=(1ll<<40);j;j>>=1)
if((sum-j)/chu>l)sum-=j;
if(sum/chu<r)
return f[t]=d*sum/chu;
}
}
inline void solve(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>s[i],s[i]=' '+s[i];
double ans=0;
for(int i=1;i<=n;i++)
{
string t;
for(int j=n;j>=1;j--)
t+=s[j][i];
ans+=dp(t);
}
if(ans>0)cout<<"Takahashi";
else cout<<"Snuke";
}代码还是很简洁的，就这我还贡献了一梭子提交。
如果你只是想过掉这道题，到这里已经足够了，可以去写代码了；但是我们还有一些问题没有处理。
比如，怎么证明局面里不存在未定义的
接下来是这类做法的证明。
\color{red}四 证明
有没有发现这个
先证明对于一个子游戏，如果
以下要求满足我们就可以证明：
如果原局面
f>0 ，如果是先手决策，至少存在一种操作，使得新局面的f\ge 0 ；如果是后手决策，后手的任何一种操作，都会使得新局面的f 仍然>0 。原局面f\le 0 的情况正好相反，类推即可。
根据求法，先手转移到的
对于一个子游戏，以上判断方法成立。而本问题中的游戏是列数个子游戏的叠加，只需将