P8394 「BalticOI 2022 Day2」Boarding Passes

一道不算难的状压。

根据期望的线性性，将组 $A$ 上船的代价拆成 $A$ 内部所有人之间的代价以及其它所有已经上船的组对 $A$ 产生的代价。

对于组 $A$ 而言，必然存在一个分界点 $p$ 满足位置 $\leq p$ 的人从左边上船，$> p$ 的人从右边上船。考虑如果 $i < j$ 且 $i$ 从右边上船，$j$ 从左边上船，容易证明将它们调整为 $i$ 从左边上船，$j$ 从右边上船代价必然减小。

假设在 $p$ 处分割时从左边上船的人数为 $x$，则从右边上船的人数为 $|A| - x$。考虑任意两对从左边上船的人，当位置在左边的人先于位置在右边的人上船时，会产生 $1$ 的代价。因为随机排列中某两个数具有特定的前后顺序的概率相等，均为 $\dfrac 1 2$，所以分割方案 $p$ 的组内贡献为 $c_A = \dfrac {x(x - 1) + (|A| - x)(|A| - x - 1)} 4$。不妨改变 $p$ 的定义为在 $A_p$ 处分割，也就是前 $p$ 个人从左边上船，后 $|A| - p$ 个人从右边上船，则 $c_A$ 是关于 $p$ 的二次函数，且具有下凸性。

考虑某一组 $B$ 对 $A$ 的贡献。如果 $A_i$ 从左边上船，那么它的贡献是 $< A_i$ 的 $B$ 的数量，从右边同理。因此，预处理出 $f_{B, A, p}$ 表示如果在 $A_p$ 处分割，那么 $B$ 对在左边上船的 $A$ 的总贡献，$g_{B, A, p}$ 表示 $B$ 对在右边上船的 $A$ 的总贡献。预处理枚举任意两组和分隔位置，时间复杂度 $\mathcal{O}(g ^ 2n)$ 或 $\mathcal{O}(gn)$，视实现细节程度而定。

考虑 $A_p$ 和 $A_{p + 1}$，因为 $< A_{p + 1}$ 的 $B$ 的数量显然不小于 $< A_p$ 的 $B$ 的数量，所以 $f_{B, A}$ 具有下凸性。同理 $g_{B, A}$ 具有下凸性。

因为我们只关心有哪些组此时已经上船，而非它们具体的上船顺序，自然考虑状压 DP $ans_S$ 表示上船的组的集合为 $S$ 时的最小代价。转移枚举不属于 $S$ 的组 $A$，然后每个可能的分割点以及每个 $B\in S$，容易计算贡献。这样暴力的时间复杂度为 $\mathcal{O}(2 ^ g gn)$（有个 $g$ 可以被均摊分析掉，但是没啥影响），无法接受。

但注意到 $c_A$，$f_{B, A}$，$g_{B, A}$ 均下凸，所以贡献单峰（显然，下凸是比单峰更强的条件），三分最优分割点位置即可。时间复杂度 $\mathcal{O}(2 ^ g g ^ 2\log n)$。

#include <bits/stdc++.h>
using namespace std;
bool Mbe;
constexpr int N = 1e5 + 5;
template <class T> inline void cmin(T &x, T y) {x = x < y ? x : y;}
int n, mx;
char s[N];
vector<int> buc[N];
long long f[15][15][N], g[15][15][N];
long long ans[1 << 15];
bool Med;
int main() {
  fprintf(stderr, "%.3lf\n", (&Mbe - &Med) / 1048576.0);
  // freopen("passes.in", "r", stdin);
  // freopen("passes.out", "w", stdout);
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for(int i = 1; i <= n; i++) {
    mx = max(mx, (int) (s[i] - 'A') + 1);
    buc[s[i] - 'A'].push_back(i);
  }
  for(int i = 0; i < mx; i++)
    for(int j = 0; j < mx; j++)
      if(i != j) {
        for(int k = 1, cur = 0; k <= n; k++) {
          f[i][j][k] = f[i][j][k - 1];
          if(s[k] == i + 'A') cur++;
          if(s[k] == j + 'A') f[i][j][k] += cur;
        }
        for(int k = n, cur = 0; k; k--) {
          g[i][j][k] = g[i][j][k + 1];
          if(s[k] == i + 'A') cur++;
          if(s[k] == j + 'A') g[i][j][k] += cur;
        }
      }
  memset(ans, 0x3f, sizeof(ans));
  ans[0] = 0;
  for(int i = 0; i < 1 << mx; i++) {
    for(int j = 0; j < mx; j++)
      if(i >> j & 1 ^ 1) {
        int l = 0, r = buc[j].size();
        auto calc = [&](int p) {
          int pos = p ? buc[j][p - 1] : 0;
          int back = buc[j].size() - p;
          long long tot = 1ll * p * (p - 1) + 1ll * back * (back - 1);
          tot >>= 1;
          for(int k = 0; k < mx; k++)
            if(i >> k & 1)
              tot += f[k][j][pos] + g[k][j][pos + 1] << 1;
          return tot;
        };
        while(l + 2 < r) {
          int m1 = l + r >> 1, m2 = m1 + 1;
          if(calc(m1) <= calc(m2)) r = m2;
          else l = m1;
        }
        long long coef = 1e18;
        for(int p = l; p <= r; p++) cmin(coef, calc(p));
        cmin(ans[i | (1 << j)], ans[i] + coef);
      }
  }
  printf("%.3lf\n", ans[(1 << mx) - 1] * .5);
  return 0;
}