题解：P8394 [BalticOI 2022] Boarding Passes (Day2)

· · 题解

题意：求

\min_{\text{组顺序},\ \text{每人选前/后}} \mathbb{E}_{\text{组内随机排列}} [\text{经过已入座乘客次数}]

由 g\leq 15，考虑状压 DP。考虑处理出任意两组之间的贡献。

由期望的线性性，有 \mathbb E[\text{经过已入座乘客次数}]=\sum_{u<v}\mathbb E[X_{u,v}]，X_{u,v} 为 u 与 v 之间产生的经过次数。

设 u 的座位为 p_u，v 的座位为 p_v，并指定 p_u<p_v：

情况 A： u 和 v 不在同一组：

  • 当 u 比 v 早登船，则 v 是否经过 u 与 v 的方向唯一相关，没有随机性。
  • 当 v 比 u 早登船时同理。

结论：对于不同组的乘客，是否产生贡献只与所属组的登船顺序及后上船组的登船方向有关，没有随机性。

情况 B： u 和 v 在同一组：

  • 当两人都从左边上时：若 u 比 v 早上，此时贡献为 1，否则贡献为 0，总贡献 E=0.5\times1+0.5\times 0=0.5；
  • 当两人都从右边上时，同理可得为 0.5；
  • 当 u 从左边，v 从右边上时，可发现无论如何不会相遇，贡献为 0；
  • 当 u 从右边，v 从左边上时，可发现必定相遇，贡献为 1；

结论：对于同一组的乘客，对期望的贡献与上船的方向组合有关，可能为 0.5，0.5，1，0。

接下来考虑序列中的逆序对（p_u<p_v 且 u 从右边上且 v 从左边上），不难发现交换 uv 一定不劣（只有 uv 之间的贡献会减少），所以必存在一个分割点 k，使在 k 左边的点均从左边上，在 k 右边的点均从右边上。

把贡献分类考虑：

Part1：组内贡献 \text{InnerContribution}(y,k)：左侧 k 个元素共 \binom k2 对，右侧共 \binom{|y|-k}2 对，总贡献为 \dfrac {\binom k2+\binom{|y|-k}2}2；

Part2：组间贡献 \text{OuterContribution}：令 C[x][y][k] 为 x 先于 y 上船，y 的分割点为 k 时对 x 的贡献，L[i] 为 x 中在 y_i 左边的数的个数，R[i] 为 x 中在 y_i 右边的数的个数，|y| 为 y 组的人数，则有

\begin{aligned} C[x][y][k]&=\sum_{i=1}^k L[i]+\sum_{i=k+1}^{|y|} R[i],\\ \end{aligned}

这个东西可以双指针预处理，代码：

因为贡献存在 0.5 为小数，为避免浮点运算，代码中所有贡献均乘以 2，即 inner 变为 \binom k2+\binom{|y|-k}2，outer 累加时 \times 2。

vector<vector<vector<int>>>C(g,vector<vector<int>>(g));
vector<int>L(n+2,0);
vector<int>R(n+2,0);
for(int x=0;x<g;++x)
    for(int y=0;y<g;++y)
    {
        if(x==y)continue;
        int m=gra[y].size();
        C[x][y].assign(m+1,0);
        for(int k=0;k<=m;++k)L[k]=R[k]=0;
        int k=0;
        int size=gra[x].size();
        for(int i=0;i<m;++i)
        {
            while(k<size&&gra[x][k]<gra[y][i])++k;
            L[i]=k,R[i]=size-k;
        }
        for(int i=1;i<=m;++i)L[i]+=L[i-1];
        for(int i=m-1;i>=0;--i)R[i]+=R[i+1];
        for(int i=0;i<=m;++i)C[x][y][i]=(i!=0?L[i-1]:0)+(i!=m?R[i]:0);
    }

预处理完就可以做 DP 了，设 dp[mask] 为已上船的组的掩码为 mask 时的最小代价，则有

dp[mask\cup y]=\min_{0\leq k\leq |y|}\left\{dp[mask]+\text{InnerContribution}(y,k)+\sum_{x\in mask}C[x][y][k]\right\}

朴素实现是 \mathcal O(2^g\cdot g\cdot n) 的，显然过不了，考虑优化。

注意到因为 x 所产生的贡献是凸的，所以可以三分出最小的 k，复杂度降至 2^g\cdot g \cdot \mathcal O(g\cdot \log n)=\mathcal O(2^g\cdot g^2\cdot \log n)

:::info[证明凸性]

下证总贡献 \text{Contribution} 为凸函数，把贡献分类考虑：

Part1：组内贡献为 \dfrac {\binom k2+\binom{|y|-k}2}2 显然下凸；

Part2：

\begin{aligned} \Delta C(k)&=C[x][y][k+1]-C[x][y][k]\\ &=\left(\sum_{i=1}^{k+1}L[i]-\sum_{i=1}^{k}L[i]\right)- \left(\sum_{i=k+1}^{|y|}R[i]-\sum_{i=k+2}^{|y|}R[i]\right)\\ &=L[k+1]-R[k+1] \end{aligned}

接下来只需证 f(k)=\Delta C(k) 递增即可，即证

\begin{aligned} f(k+1)-f(k)&=(L[k+2]-L[k+1])-(R[k+2]-R[k+1])\geq 0\\ \end{aligned}

即可。又因为组内各元素位置单调不降，所以 L 单调不降，R 单调不增，所以等式右边恒非负，得证。

综上，\text{Contribution} 为凸函数。

:::success[完整代码]

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int INF=0x3f3f3f3f3f3f3f3f;
constexpr int maxg=15;
int toint[256];
int dp[1<<maxg];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(toint,-1,sizeof(toint));
    memset(dp,0x3f,sizeof(dp));
    string s;
    cin>>s;
    int n=s.size();
    s=' '+s;
    int g=0;
    vector<vector<int>>gra;
    for(int i=1;i<=n;++i)
    {
        if(toint[s[i]]==-1)
        {
            toint[s[i]]=g++;
            gra.emplace_back();
        }
        gra[toint[s[i]]].emplace_back(i);
    }
    vector<vector<vector<int>>>C(g,vector<vector<int>>(g));
    vector<int>L(n+2,0);
    vector<int>R(n+2,0);
    for(int x=0;x<g;++x)
        for(int y=0;y<g;++y)
        {
            if(x==y)continue;
            int m=gra[y].size();
            C[x][y].assign(m+1,0);
            for(int k=0;k<=m;++k)L[k]=R[k]=0;
            int k=0;
            int size=gra[x].size();
            for(int i=0;i<m;++i)
            {
                while(k<size&&gra[x][k]<gra[y][i])++k;
                L[i]=k,R[i]=size-k;
            }
            for(int i=1;i<=m;++i)L[i]+=L[i-1];
            for(int i=m-1;i>=0;--i)R[i]+=R[i+1];
            for(int i=0;i<=m;++i)C[x][y][i]=(i!=0?L[i-1]:0)+(i!=m?R[i]:0);
        }
    auto calc=[&](unsigned mask,int y,int k)
    {
        int ans=0;
        int m=gra[y].size();
        int inner=k*(k-1)/2+(m-k)*(m-k-1)/2;
        int outer=0;
        for(int x=0;x<g;++x)
            if(mask>>x&1)outer+=C[x][y][k]*2;
        return inner+outer;
    };
    auto find=[&](unsigned mask,int y)
    {
        int l=0,r=gra[y].size();
        while(r-l>=10)
        {
            int lmid=(l*2+r)/3;
            int rmid=(l+r*2)/3;
            if(calc(mask,y,lmid)>calc(mask,y,rmid))l=lmid;
            else r=rmid;
        }
        return make_pair(l,r);
    };
    dp[0]=0;
    for(unsigned mask=0;mask<1<<g;++mask)
    {
        for(int y=0;y<g;++y)
        {
            if(mask>>y&1)continue;
            auto [l,r]=find(mask,y);
            for(int k=l;k<=r;++k)
            {
                dp[mask|1<<y]=min(dp[mask|1<<y],dp[mask]+calc(mask,y,k));
            }
        }
    }
    unsigned full=(1<<g)-1;
    cout<<fixed<<setprecision(10)<<1.0L*dp[full]/2;
}

:::