Atcoder abc224

發表於 更新於 分類於 ， Disqus： 文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘
G(概率论,二分)H(线性规划,对偶问题,费用流,MCMF)

G - Roll or Increment

https://atcoder.jp/contests/abc224/tasks/abc224_g

1~N 骰子

初始S, 得分f(X) = X

A元, 让得分+1

B元, 重新转

求最小期望代价, 让得分为T

范围

N 1e9

A,B [1,1e9]

2s

1024 mb

我的思路

日常不会概率论

猜一个

S < T

直接通过A, (T-S)A

转一次的期望 E

(N-T)/N * (B+E), 大于T 部分的贡献

1/N ( min(0,B+E) + min(A,B+E) + min(2A,B+E) + … + min((T-1)A,B+E)), $\le T$ 部分的贡献

$E = \frac{N-T}{N} \cdot (B+E) + \frac{1}{N} ( min(0,B+E) + min(A,B+E) + min(2A,B+E) + \cdots + min((T-1)A,B+E))$

若能求出E, 就做出来了

转化一下

$NB + \sum_{i=0}^{T-1} \text{min}(iA-(B+E),0) = 0$

只有E是变化的, 随着E 增大, 表示式变小, 单调, 可二分

好像还真就过了

代码

https://atcoder.jp/contests/abc224/submissions/33889681

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
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double LD;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read


int main(){
  ll N = read();
  ll S = read();
  ll T = read();
  ll A = read();
  ll B = read();
  auto calc = [=](LD E){
    ll l = 0;
    ll r = T-1;
    if(r*A-B-E<=0){
      l = r;
    }else{
      while(l+1<r){
        ll m = (l+r)/2;
        if(m*A-B-E<=0) l = m;
        else r = m;
      }
    }
    // nb + sum min(iA-B - E,0), i = 0~T-1;
    return N * B+ A * l * (l+1) / 2 - (B+E) * (l+1) ;
  };
  LD LE = 0;
  LD RE = A * T;
  while(calc(RE) > 0) RE *= 2;
  rep(t,0,10000){ // E增, 和减
    LD E = (LE+RE)/2;
    (calc(E) > 0 ? LE : RE) = E;
  }
  LD ans = B + LE;
  if(S <= T) ans = min(ans,(LD)((T-S) * A));
  printf("%.15Lf",ans);
  return 0;
}

H - Security Camera 2

https://atcoder.jp/contests/abc224/tasks/abc224_h

二分图, 左侧L个点,右侧R个点

在点i上每次安装摄像头, 有 Ai(左侧),Bj(右侧) 的代价, 一个点可安多次

目标 让 i上安装的个数 + j上安装的个数 >= Cij

一左一右侧

问最小安装代价

范围

L,R 100

Ai,Bi [1,10]

Cij, [0,100]

2s

1024mb

我的思路

这个数还不少, 而代价的范围还挺小的?

然后有点费用流又有点2sat的感觉

emmmm

题解

这个题主要在练习线性规划的技术和,对偶问题的创造能力

首先是构造线性规划

li 表示左侧每个安装的个数

ri 表示左侧每个安装的个数

要求 $min(\sum_{i} A_il_i + \sum_{i}B_ir_i)$

限制

$li+rj \ge C_{i,j}$

$li \ge 0, ri \ge 0$ 且都是整数(需要存在整数的方案最优)

然后 构造对偶问题

对于限制

$l_i+r_j \ge C_{i,j}$

同时乘上$k_{i,j} \ge 0$

$k_{i,j}(l_i+r_j) \ge k_{i,j} C_{i,j},$

对于$k_{i,j},p_i,q_i \ge 0$

$\sum_{i,j} k_{i,j} (l_i+r_j) + \sum_i p_i l_i + \sum_i q_i r_i \ge \sum_{i,j} k_{i,j} C_{i,j}$

这样不等式左边如果和目标一致,那么右边的值就是它的下界

也就是 对于任意k的选取

找p和q, 让 $\sum_{i,j} k_{i,j} (l_i+r_j) + \sum_i p_i l_i + \sum_i q_i r_i = \sum_i (\sum_j k_{i,j} + p_i) l_i + \sum_j (\sum_i k_{i,j} + q_j) r_j = \sum_i A_il_i + \sum_j B_jr_j.$

那么 原目标 大于右侧的$\sum$

也就是任何满足$0\le \sum_j k_{i,j} \le A_i, 0 \le \sum_i k_{i,j} \le B_j $的 $\forall k$, 会产生不大于原目标的$\sum_{i,j} k_{i,j} C_{i,j}$

那么 原目标 $\ge max(\sum_{i,j} k_{i,j} C_{i,j})$

emmmm 有个问题是 只是证明了, min(原) >= max(sum kc)

这个等号好像没证明????

怎么算对偶问题呢

就是最小费用流了

左点A, 右点B

源到Ai, 容量Ai, 单位代价0

Bi到汇, 容量Bi, 单位代价0

Ai到Bj, 容量无限, 单位代价$-C_{i,j}$

求最大流的最小代价

注意到atcoder自带的mcmf(min cost max flow)是无法处理负边权的, 让所有每单位流量增加max(c) 即可

手写的话, 也可以就是做最大流时找新的流的过程用spfa来更新最近距离

之前做abc 214 也写到过mcmf,见下方

代码

https://atcoder.jp/contests/abc224/submissions/33906446

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
#include <bits/stdc++.h>
#include <atcoder/mincostflow>
using namespace std;

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

int c[110][110];

int main(){
  int L = read();
  int R = read();
  atcoder::mcf_graph<int, int> network(L+R+2); // 点个数
  int S = L+R; // 源
  int T = S+1; // 汇
  rep(i,0,L) network.add_edge(S,i,read(),0); // ai
  rep(j,0,R) network.add_edge(L+j,T,read(),0); // bi
  int maxc = 0;
  rep(i,0,L) rep(j,0,R) maxc = max(maxc, c[i][j] = read());
  rep(i,0,L) rep(j,0,R) network.add_edge(i,L+j,10,maxc-c[i][j]); // 保证全部非负
  auto [maxflow, mincost] = network.flow(S,T);
  printf("%d\n", maxflow * maxc - mincost); // - (mincost - maxflow * maxc)
  return 0;
}

总结

G

概率论, 竟然对了

H

线性规划,对偶问题

对偶问题学了几次感觉也没有悟到

但是从技术上讲,应该能看出这个类型的, 这里没看出是线性规划问题也是有问题

有一说一,这atcoder 题解真的细, 我之前做cf,和一些其它的线性规划对偶, 都是直接甩公式, 然后找了各种博客,都在那里比喻来比喻去的, 这里竟然数学公式教会了我证明的一部分, 而且其实过程也没几步

Atcoder yyds

参考

官方题解

abc 214 mcmf

cf 1969 线性规划对偶

wata 对偶讲义