题解：P17092 [ICPC 2017 Qingdao R] Battle in Two Pairs of Heroes

· · 题解

题意简述

Alice 与 Bob 各有两名英雄。每回合，行动方的每名存活英雄都选择一名存活敌人攻击。双方均采用最优策略。分别判断 Alice 先手和 Bob 先手时的胜者，再按题意输出三种结论。

解题思路

用五元组 (a_1,a_2,b_1,b_2,t) 表示局面，t=0 表示轮到 Alice，t=1 表示轮到 Bob。生命值降到非正数后统一记为 0。

定义 F(s) 表示从局面 s 开始，Alice 是否必胜。若 Bob 的两名英雄均死亡，则 F(s)=1；若 Alice 的两名英雄均死亡，则 F(s)=0。其余状态满足：

F(s)= \begin{cases} \displaystyle\bigvee_{u\in\operatorname{next}(s)}F(u), & t=0 \\ \displaystyle\bigwedge_{u\in\operatorname{next}(s)}F(u), & t=1 \end{cases}

每次攻击至少让一名存活英雄的生命值严格下降。因此，四个生命值之和沿转移严格递减，搜索图没有环，可以直接记忆化。

生成行动时，先收集双方仍存活的英雄。行动方至多有两人，目标也至多有两人，所以攻击分配最多只有 2^2=4 种。代码用进制枚举统一生成这些分配，不分别讨论存活人数。

若两种行动得到的敌方生命值分别为 (x_1,x_2) 与 (y_1,y_2)，并且：

\begin{aligned} x_1 & \le y_1 \\ x_2 & \le y_2 \end{aligned}

则第一种行动不会更差。它让两名敌人的生命值都不更多，之后可以沿用第二种行动对应的策略。因此，只保留按坐标偏序极小的后继。

单纯记忆化仍可能接近四维生命值空间的边界。还需要利用胜负的单调性。把原生命值改写为对 Alice 越大越有利的坐标：

z=(a_1,a_2,99-b_1,99-b_2)

增加任意一个 z_i，不会把 Alice 必胜局面变成必败局面。下面分别说明两种行动方。

Alice 行动时，较有利局面至少保留原局面中全部存活的 Alice 英雄，并且 Bob 的生命值不更高。Alice 可以选择与原策略相同的攻击目标，得到一个仍不弱于原后继的局面。

Bob 行动时，从较有利局面出发，Bob 的每种攻击都能在原局面中找到相同的攻击分配。原局面的 Alice 生命值不更高，Bob 生命值不更低，所以原后继不会比新后继更有利于 Alice。由归纳可得胜负关于每个 z_i 单调。

固定行动方和另外三个坐标，只观察 z_i。这一条长度为 100 的序列必定先是 Alice 必败，后是 Alice 必胜。对每条序列维护两个边界：

查询新状态时，只要某个方向满足 z_i\ge\text{win}，就能由单调性判定必胜；若满足 z_i<\text{lose}，就能判定必败。只有位于所有已知边界之间的状态才继续递归。

通过边界推导出的状态不反过来更新边界。只有真正完成极小极大搜索的状态才会写入边界和精确记忆化表，这样每条边界都始终有一个已求值状态作为依据。

四个生命值都小于 100。删除某一坐标后，其余三个坐标可以用一个 0 到 999999 的整数编码，所以边界数组的大小为 2\times4\times100^3。

最后分别求初始状态在 t=0 与 t=1 时的值。两者都为真时 Alice 无论先后手都胜；两者都为假时 Bob 无论先后手都胜；否则胜者取决于先手。

设真正展开的状态数为 S。每个状态最多生成四个行动，边界查询、后继去重和支配判断都是常数规模操作，期望时间复杂度为 O(S)。边界数组空间为 O(100^3)，记忆化空间为 O(S)。

正确性证明

每次转移都会严格降低生命值总和，所以递归一定到达某方全灭的终止状态。Alice 回合对后继取或，准确表达她可以主动选择一种获胜行动；Bob 回合对后继取与，准确表达 Alice 必须抵抗 Bob 的所有选择。因此，不考虑剪枝时，记忆化搜索正是有限完全信息游戏的极小极大值。

若一个后继的两名敌方英雄生命值均不高于另一个后继，当前行动方可以把前者视作后者的强化结果。更早死亡的敌方英雄只会失去攻击能力，不会获得新行动。因此删除被支配后继不会改变当前状态的胜负。

变换后的四个坐标都与 Alice 的优势同向。增加 Alice 生命值不会减少她的可用行动，减少 Bob 生命值不会增强 Bob 的行动。对剩余回合数归纳，若状态 x 不劣于状态 y 且 y 为 Alice 必胜，则 x 也为 Alice 必胜。故每条固定三坐标的一维序列确实只有一个由败到胜的分界。

win 只由已求出的必胜状态更新，lose 只由已求出的必败状态更新。单调性保证边界外侧的推断全部正确，而边界之间仍交给完整搜索。因此，剪枝不会产生错误判定。

程序分别精确得到两种先手情况下 Alice 是否必胜，并按这两个布尔值分类输出，所以最终结论正确。

参考代码

#include <bits/stdc++.h>
using namespace std;

using uc=unsigned char;
using ui=unsigned int;
using hp=array<int,4>;
const int M=1000005;
int d[2][2][2];
uc win[4][2][M],lose[4][2][M];
unordered_map<ui,uc> mem;
int line(const hp &z,int p)
{
    int res=0;
    for(int i=0;i<4;i++)if(i!=p)res=res*100+z[i];
    return res;
}
hp change(const hp &h)
{
    return {h[0],h[1],99-h[2],99-h[3]};
}
int ask(const hp &h,int t)
{
    hp z=change(h);
    for(int i=0;i<4;i++)
    {
        int s=line(z,i);
        if(z[i]>=win[i][t][s])return 1;
        if(z[i]<lose[i][t][s])return 0;
    }
    return -1;
}
void upd(const hp &h,int t,bool w)
{
    hp z=change(h);
    for(int i=0;i<4;i++)
    {
        int s=line(z,i);
        if(w)win[i][t][s]=min(win[i][t][s],uc(z[i]));
        else lose[i][t][s]=max(lose[i][t][s],uc(z[i]+1));
    }
}
vector<hp> next(const hp &h,int t)
{
    int from=t?2:0,to=t?0:2;
    int a[2],b[2],ac=0,bc=0;
    for(int i=0;i<2;i++)
    {
        if(h[from+i])a[ac++]=i;
        if(h[to+i])b[bc++]=i;
    }
    int ways=1;
    for(int i=0;i<ac;i++)ways*=bc;
    vector<hp> q;
    for(int i=0;i<ways;i++)
    {
        hp z=h;
        int x=i;
        for(int j=0;j<ac;j++)
        {
            int k=b[x%bc];
            x/=bc;
            z[to+k]=max(0,z[to+k]-d[t][a[j]][k]);
        }
        q.push_back(z);
    }
    sort(q.begin(),q.end());
    q.erase(unique(q.begin(),q.end()),q.end());
    vector<hp> res;
    for(int i=0;i<q.size();i++)
    {
        bool bad=0;
        for(int j=0;j<q.size();j++)
        {
            if(i==j)continue;
            if(q[j][to]<=q[i][to]&&q[j][to+1]<=q[i][to+1])bad=1;
        }
        if(!bad)res.push_back(q[i]);
    }
    sort(res.begin(),res.end(),[to](const hp &x,const hp &y)
    {
        return x[to]+x[to+1]<y[to]+y[to+1];
    });
    return res;
}
ui encode(const hp &h,int t)
{
    ui res=0;
    for(int i=0;i<4;i++)res=res*100+h[i];
    return res*2+t;
}
bool dfs(const hp &h,int t)
{
    if(!h[2]&&!h[3])return 1;
    if(!h[0]&&!h[1])return 0;
    ui s=encode(h,t);
    auto it=mem.find(s);
    if(it!=mem.end())return it->second-1;
    int k=ask(h,t);
    if(k!=-1)return k;
    bool ans=t;
    for(auto z:next(h,t))
    {
        bool w=dfs(z,t^1);
        if(w!=t)
        {
            ans=w;
            break;
        }
    }
    mem[s]=ans+1;
    upd(h,t,ans);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        hp h;
        for(int i=0;i<4;i++)cin>>h[i];
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)cin>>d[0][i][j];
        }
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)cin>>d[1][i][j];
        }
        mem.clear();
        mem.reserve(1<<18);
        mem.max_load_factor(0.7);
        memset(win,100,sizeof win);
        memset(lose,0,sizeof lose);
        bool x=dfs(h,0),y=dfs(h,1);
        if(x&&y)cout<<"Alice wins"<<'\n';
        else if(!x&&!y)cout<<"Bob wins"<<'\n';
        else cout<<"It depends"<<'\n';
    }
    return 0;
}