Atcoder abc231

發表於 更新於 分類於 ， Disqus： 文章字數： 2k 所需閱讀時間 ≈ 7 分鐘
G(概率论,排列,组合)H(图论,边覆盖,费用流)

https://atcoder.jp/contests/abc231/tasks

G - Balls in Boxes

n个盒子, 初始第i个盒子有ai个球

k次操作

每次 等概率选一个盒子, 增加1个球

分数 = 最终每个盒子的球的个数之乘积

求分数期望 mod 998244353

范围

n 1000

k 1e9

ai [0, 1e9]

2s

1024 mb

我的思路

感觉上可以 做n和n-1的关系, 然后直接算频次, 最后除总次数 转成概率

F(n,k) = 前n个所有方案的乘积和, Ans = F(n,k) / n^k

对于最后一个盒子, 选择了j次, 对应的方案乘积和为 C(k,j) * F(n-1,k-j) * (a[n]+j)

F(n,k) = sum (a[n]+j) * F(n-1,k-j) * C(k,j), j=0..k

这里n虽然小, 但是k很大, 上面这个显然TLE, 如果能搞到n^2 左右的就好了

C(k,j) 的部分拆出来 分配给F的分母可以简化,但是依然没有去掉k的维度

题解

$E\lbrack \prod_i(A_i+X_i) \rbrack$

$E\lbrack(A_1+X_1)(A_2+X_2)\rbrack = E\lbrack A_1A_2\rbrack + E\lbrack A_1X_2\rbrack + E\lbrack X_1A_2\rbrack+ E\lbrack X_1X_2\rbrack$

$E\left[\prod_{i=1}^{N} (A_i+X_i)\right]=\sum_{n=0}^{N}S_{N,n}(A_1,\ldots,A_N)E\left[\prod_{i=1}^{N-n}X_i\right],$

$S_{N,n} $是从传入的$N$个中取n个的所有方案

$dp[i][j] = S_{i,j} (A_1\cdots A_i)$

考虑第$i+1$个是否选择有转义 $dp[i+1][j] = dp[i][j] + dp[i][j-1]A_{i+1}$

暴力n^2就好

当第j次操作选择第i个盒子 $X_{i,j} = 1$, 否则$X_{i,j} = 0$

$E\left[\prod_{i=1}^{n}X_i\right] = E\left[\prod_{i=1}^{n} \sum_{j=1}^{K}X_{i,j} \right]=\sum_{j_1,\ldots,j_n}E\left[\prod_{i=1}^{n}X_{i,j_i}\right].$, 先展开$X_i$ , 再像上面乘法分配展开,和期望展开

对于右侧$j_i$ 要两两不同则期望为$(\frac{1}{N})^n$, 否则为$0$(不能第j次 选多个盒子)

因此为排列数, $A(K,n)$,

暴力算

代码

https://atcoder.jp/contests/abc231/submissions/34624129

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
#define rep(i,a,n) for (int i=a;i<(int )n;i++)
int read(){int r;scanf("%d",&r);return r;} // read

mint a[1010];
mint f[1010][1010]; // [0~n个][选0~n个] = 乘积的和, 可以滚动优化掉一维但没必要
int main(){
  int n = read();
  int k = read();
  rep(i,0,n) a[i] = read();
  f[0][0]=1;
  rep(i,1,n+1) rep(j,0,i+1) f[i][j] = f[i-1][j] + (j?f[i-1][j-1]*a[i-1]:0);
  mint c=0;
  mint x=mint(1)/n;
  mint fac=1;
  rep(j,0,std::min(n,k)+1) {
    c+=f[n][n-j]*fac;
    fac*=x*(k-j);
  }
  printf("%d\n",c.val());
  return 0;
}

H - Minimum Coloring

h行,w列 矩阵

N个白色格子, 坐标分别(Ai,Bi), 需要代价Ci 让第i个变成黑色

求 让每行每列至少一个黑色的最小代价

保证至少有方案

范围

h,w 1e3

n 1e3

ci [1,1e9]

2s

1024mb

我的思路

感觉之前做过类似的, 像是网络流 最小割

整体思路是 把所有贡献变成正, 然后对源和汇分别定义 选还是不选, 然后用最小割对图的划分 有意义 选的代价 和 不选的代价

但是这里, 选的代价很好表示, 但不选的代价(全部不选则无限大代价) 不知道如何用点表示

即使拖出一个行节点, 倒是可以表示和S,T的边关系了, 却不知道怎么表示Pi,j和Rowi的关系

题解

图G

点, X_i 对应行 Y_j 对应列

边就是$(X_i,Y_j)$, 代价是$C_{i,j}$

求最小加权边覆盖(选边, 让所有点至少被选择一次)

直观地考虑“我们可以减少多少成本，而不是‘在每一行和每个顶点中选择成本最低的一块

  1. 随机选择边集E的子集$E_1$
  2. 对于每个不被$E_1$覆盖的点v, 选择一个v相连的最小代价的边, 允许重复选重复代价, E2 = E1 + 这些边, (注意到这些边又E_1唯一决定

虽然说可能 答案的边集不包含任何最小代价边,(1-3(2),1-4(1),2-4(2)) 但是第一步可能直接就得到答案

同时,在最优解中, 第一步的边不会有两边选了同一个点!!!

证明: 比如 a-b, a-c, 那么如果a-b 是b的最小边, 删掉a-b 结果不会更小,如果a-b不是b的最小边, 那么去掉a-b, 去选b的最小边, 得到更小的值 但是不小的点集, 因此去选都可以先不选, 得证

令$V_1$ 为$E_1$覆盖了的点集

令$v$的最小代价边权为$C_v$, 那么对于

$cost(E_2) = cost(E1) + \sum_{v \in V\setminus V_1} C_v$

$cost(E_2) = cost(E1) + \sum_{v \in V} C_v - \sum_{v \in V_1} C_v$

定义$c(e) = cost(e) - C_{e_u} - C_{e_v}$, $c(e)=$ 边代价 减去两点的最小权

$cost(E_2) = cost(E1) + \sum_{v \in V} c(e)$

而 第一个是定值, 那么就是要最小化第二个值

然后用 最小费用流

建图

$S \to X_i$ 容量1,单位代价0

对于每个$(X_i,Y_j)$, 边$X_i \to Y_j$ 容量1,单位代价 $c((X_i,Y_j)$, 因为不选就是0, 因此非负的边不要加

$Y_i \to T$ 容量1,单位代价0

任意流量的最小费用就是答案

注意MCMF不要负边权, 因此, 让所有流的单位费用增加 BIG = MAX(-c)

$S \to X_i$ 容量1,单位代价0

对于每个$(X_i,Y_j)$, 边$X_i \to Y_j$ 容量1,单位代价 $c((X_i,Y_j) + $

$Y_i \to T$ 容量1,单位代价0

变成 $= min(Cost_i - i*BIG)$, 其中i为流量

还可以用atcoder的库mcf_graph 的slope(S,T) -> std::vector<std::pair<Cap, Cost>>

得到 不同流量(注意到这里只需要关注斜率变化的点)对应的最小代价, 相当于一个凹函数被一个一次函数切

代码

https://atcoder.jp/contests/abc231/submissions/34624860

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#include <atcoder/all>
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;} // read
const ll BIG=2e9;

int main(){
  int h = read(); // height
  int w = read(); // width
  int n = read(); // 点
  std::vector<int>hmin(h+1,1e9),wmin(w+1,1e9);
  std::vector<std::tuple<int,int,int>>p;
  rep(i,0,n){
    int a = read(); // 行 1-index
    int b = read(); // 列 1-index
    int c = read(); // 代价
    hmin[a]=std::min(hmin[a],c);
    wmin[b]=std::min(wmin[b],c);
    p.push_back({a,b,c});
  }
  const int S = 0; // source
  const int T = h+w+1; // sink
  atcoder::mcf_graph<int,ll>g(T+1);
  rep(i,1,h+1) g.add_edge(S  ,i,1,0); // S->Xi(行) [1..h]
  rep(i,1,w+1) g.add_edge(h+i,T,1,0); // Y_i(列)[h+1..h+w] -> T
  for(auto [a,b,c]:p) if(c < hmin[a]+wmin[b]/*非负的不会选*/) g.add_edge(a,h+b,1,c-hmin[a]-wmin[b]+BIG);
  ll ans=0;
  for(auto[cap,cost]:g.slope(S,T)) ans=std::min(ans,cost-BIG*cap);// 斜率优化, 只用关心斜率变化的点
  rep(i,1,h+1) ans+=hmin[i]; // 常数的部分 sum C_v
  rep(i,1,w+1) ans+=wmin[i];
  printf("%lld\n", ans);
}

总结

G

概率论完全不会.. 忘记了哪些可以乘法加法, 啥变化规律 都忘了,

但其实也可以从积分/离散的期望定义来看, 不就是 int p(f(x)+g(x)) dx, = int p f(x) dx + int p g(x) dx, 所以加法是可拆的

这里虽然加了以后每个位置互不相同,但是如果把加的部分单独拎出来看, 就没有不同, 所以其实这里第一步做的期望拆分, 也就是把原来就有的ai和操作中对第i个增加的xi拆开来算

H

网络流会了一点, 但一点不会, 图论完全不会

这个神奇的边覆盖,图匹配 = min(随机(不重点的边) + 未选点的最小边集)

然后就是费用流的一种使用吧, 以及atcoder 提供的mcf和slope方法

参考

官方题解