Atcoder abc305

發表於 更新於 分類於 ， Disqus： 文章字數： 3.6k 所需閱讀時間 ≈ 12 分鐘
Ex(Submodular set function,Alien DP,d-edge-shortest-path-monge)

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

Ex - Shojin

N个问题, 难度(Ai,Bi)

选择$D \in [1,N]$天 完成所有N个问题，即把N个问题分成D个连续非空子区间

疲劳x 每天初始 = 0，每天完成当前的区间中的问题

区间内问题顺序可以任意调整，每次完成一个问题后 x_new = A x_old+B

给定X, 问 min D, 使得 sum x_每天结束<= X

输出 (min D, 对于 min D时最小的sum x_每天结束)

n 2e5

X 1e8

ai [1,1e5]

1<= bi

sum bi <= X

3s

1024mb

我的思路

先说一天内，如果指定了区间

先i后j: $a_j(a_i x + b_i) + b_j$

先j后i: $a_i(a_j x + b_j) + b_i$

如果要 $a_j(a_i x + b_i) + b_j < a_i(a_j x + b_j) + b_i$

即 $a_j b_i + b_j < a_i b_j + b_i$

即 $(a_j-1) b_i < (a_i-1) b_j$

即 $\frac {a_j-1}{b_j} < \frac{a_i-1}{b_i}$

即每个元素 可以按照key = $-\frac{a-1}{b}$ 排序

反过来排序则是最大

问题其实变成对于给定D, 求min

对于min显然 随着D增加，min 单调递减，因为至少有一天两个问题，而后一个问题的额外代价 是 (Ax+B)-x = (A-1)x+B, 而单独放一天则是B, 而A>=1

有一个巨大的dp

dp[i][d] 以i结束，i前面划分了d天的 最小消耗

就是求 dp[n][min d] <= x

dp[i][d] = min(dp[j][d-1] + cost[j+1..i]), j<i

首先 状态就n^2,空间就n^2 ,转移看上去要n^2,时间就是n^4

先说能否降低到n^3, 也就是cost[i...j] 有没有什么快速的计算方法或者预处理

显然x=Ax+B可以用矩阵乘法表示

那么就可以用线段树按 上面 -(a-1)/b 的顺序 维护

一个区间就是区间内的变成 对应的矩阵，而区间外的 变成 单位矩阵

那么计算一个区间cost[i...j] 无非就是cost[i...j-1] 基础上让 j在线段树中对应的 变为对应矩阵再计算完整线段树的 矩阵乘法结果，

这样显然 循环 遍历i,j 能 n^2 log n 算出所有cost[i..j]

至少时间复杂度变成 n^3 + n^2 log n

感觉 还缺了什么数学性质

但对于相邻的两个区间，并不知道 相邻位置放在哪个区间好

因为并不知道 它 排序后的位置，

虽然可以 预估它放最前 和 最后的贡献变化，一个是预估，另一个是需要他前后的区间的信息

题解

也是先考虑区间内，得到一样的性质

令f(S) = 可重集合S最小代价, 有性质 $S\subseteq T \rightarrow f(S + \lbrace p \rbrace) - f(S) \le f(T + \lbrace p \rbrace) - f(T)$

证明:

若$A_p = 1$, 则上式 为等式，因为p放在最后，额外贡献就是$B_p$

考虑$A_p\ge 2$

1
2
T:  v1,...,vi,p,vi+1,...,vn
S:  w1,...,wj,p,wj+1,...,wm

显然w是v的子序列

将解决问题的操作看作是仿射变换的应用。（换句话说 (x,1) 乘上 一系列矩阵）

首先显然 如果序列s是t的子序列，则显然 s 处理后的 最终的合并后的 $(A_s,B_s)\le (A_t,B_t)$

1
2
3
4
5
T:  (a',b'),(A_p,B_p),(c',d')
S:  (a,b),(A_p,B_p),(c,d)

(a',b') >= (a,b)
(c',d') >= (c,d)

$f(S+\lbrace p \rbrace) - f(S)$

$=[(c(A_p(ax+b)+B_p)+d)-(c(ax+b)+d)]_{x=0}$

$=(c(A_pb+B_p)+d)-(cb+d)$

$=c((A_p-1)b+B_p)$

$\ge c’((A_p-1)b’+B_p)$

$= f(T+\lbrace p \rbrace)-f(T)$

得证

即是 任何一个元素加入到集合 的贡献 不小于加入该集合子集的贡献

性质 $A\ge 2$时, 有$f(S)+f(T)\le f(S\cup T) + f(S\cap T)$

证明:

$S=T$时显然等式成立

而注意到 令$U=S-(S\cap T) = (S\cup T) -T$且$(S\cap T)\subseteq T$

根据上面的 $f(S) - f(S\cap T) \le f(S\cup T) - f(T)$ 无非是对$U$中的逐个加入 再不等式 合并

得证

The inequalities in these two propositions are called diminishing marginal utility and submodularity (with inequality sign flipped);  it seems that their equivalence are widely known in the field of combinational optimization.

Mongeness and Alien DP(王钦石二分,”wqs 二分搜索”或“Lagrange 松弛”)

考虑 $A_i \ge 2$

简化期间，重新表述为最短路问题，定义N顶点有向有边权图G, 从顶点u到顶点v有向边成本$c(u,v)$为 $[u+1,v]$所需要的问题, K天的方案可以看成图G上 K条边构成的$0-N$的路径,

对于$0\le i< j< k < l \le N$有

$c(i,l)+c(j,k) \ge c(i,k)+c(j,l)$, 根据上面证明的性质

这个性质称为 Mongeness 或者四边形不等式

$d(k) = k$条边的最短长度,

下凸性$d(n)-d(n-1) \ge d(n-1)-d(n-2)$

拉格朗日 对偶问题

$\mathcal{P}$ 是图G中所有0->N的路径集合

$||P||$表示路径$P$的长度(边的条数)

$c(P)$表示边权和

对于$\forall \lambda \in \mathbb{Z}$

长度$d$的最小代价 $\displaystyle \min_{P\in \mathcal{P},||P||=d}c(P) =\min_{P\in \mathcal{P},||P||=d} (c(P)+\lambda(||P||-d))$, 显然 多出来的为0

$\displaystyle \ge \min_{P\in \mathcal{P}} (c(P)+\lambda(||P||-d))$, 去掉了底部的限制, 拉格朗日 松弛, ($X\ge min(X,…)$的原理)

从而以下式子成立

$\displaystyle \min_{P\in \mathcal{P},||P||=d}c(P) \ge \max_{\lambda\in\mathbb{Z}}\min_{P\in\mathcal{P}}(c(P)+\lambda(||P||-d))$

这解释为调整$\lambda$ 获得最佳下限, 就涉及拉格朗日对偶问题, 一般来说，等毫不成立，在这个问题中等号成立(下面会证明)

用$P^*_k$表示长度$k$的路径的一个最小代价方案

定理 1 $c(P^*k)-c(P^*{k-1}) \le c(P^*_{k+1})-c(P^*_{k})$

若存在$||P||=||P’||=k$ 两条路径满足 $c(P^*_{k+1})+c(P^*_{k-1})\ge c(P)+c(P’) \ge c(P^*_k)+c(P^*_k)$， 则可证明

注意到右侧的不等式显然，因为$P^*$是最优的，现在考虑能否找到满足左侧的不等式

$P^*_{k-1} = (s_0,s_1,\cdots,s_{k-1})$

$P^*_{k+1} = (t_0,t_1,\cdots,t_{k+1})$

这两个点列的首尾相同

  • 若存在 $s_i = t_{i+1}$
    • 令$P =(s_0,s_1,\cdots,s_i,t_{i+2},t_{i+3},\cdots,t_{k+1})$
    • 令$P’ =(t_0,t_1,\cdots,t_{i+1},s_{i+1},t_{i+2},\cdots,s_{k-1})$
    • 这样 相当于两条路径在一个固定距离的交叉点交换， $c(P^*_{k+1})+c(P^*_{k-1}) = c(P)+c(P’)$ 上面左侧不等式的等号成立
  • 则存在 $s_i < t_{i+1} \land s_{i+1} > t_{i+2}$, 因为 $s_0 = 0 < t_1, s_{k-1}=N-1 > t_{k}$, 所以如果没有相等，则总存在一个i满足
    • 令$P =(s_0,s_1,\cdots,s_i,t_{i+2},t_{i+3},\cdots,t_{k+1})$
    • 令$P’ =(t_0,t_1,\cdots,t_{i+1},s_{i+1},t_{i+2},\cdots,s_{k-1})$
    • 这样的话有 $s_i < t_{i+1} < t_{i+2} < s_{i+1}$
    • 正是 上面 需要的前提条件 monge性（四边形不等式)
    • $c(s_i,s_{i+1}) +c(t_{i+1},t_{i+2}) \ge c(s_i,t_{i+2}) + c(t_{x+1},s_{x+1})$
    • 即$c(P^*_{k+1})+c(P^*_{k-1}) \ge c(P)+c(P’)$ 成立

所以定义1得证明, 即$c(P^*_k)$的下凸性

定理2 存在$\lambda^\in \mathbb{Z}$使得有 $\displaystyle P^d\in \mathrm{argmin}{P\in \mathcal{P}} (c(P)+\lambda^*(||P||-d))$ 成立

根据定理1,可以找到$\lambda^*$满足$- (c(P _ {d + 1} ^ {\ast}) - c(P _ d ^ {\ast})) \leq \lambda ^ {\ast} \leq - (c(P _ d ^ {\ast}) - c(P _ {d - 1} ^ {\ast}))$

那么只需要证明对于$\forall k, c(P^*_k)+\lambda^*(k-d) \ge c(P^*_d)$,且存在取等,即可证明定理2, 因为如果 k不是最短的路径的话$c(P_k)+\lambda^*(k-d) \ge c(P^*_k)+\lambda^*(k-d)$ 只会更大

  • $k=d$
    • $c(P^*_d) + \lambda^*(d-d)$
    • $=c(P^*_d)$
  • $k < d$
    • $c(P^*_k) + \lambda^*(k-d)$
    • $=c(P^*d) - \sum{i=k}^{d-1}(c(P^*_{i+1})-c(P^*_i)) + \lambda^*(k-d)$
    • $\ge c(P^*d) - (d-k)(c(P^*{d})-c(P^*_{d-1})) + \lambda^*(k-d)$ (根据定理1)
    • $\ge c(P^*_d) + (d-k)\lambda^* + \lambda^*(k-d)$ (根据$\lambda^*$的取值范围)
    • $= c(P^*_d)$
  • $k > d$
    • $c(P^*_k) + \lambda^*(k-d)$
    • $=c(P^*d) + \sum{i=d}^{k-1}(c(P^*_{i+1})-c(P^*_i)) + \lambda^*(k-d)$
    • $\ge c(P^*d) + (k-d)(c(P^*{d})-c(P^*_{d-1})) + \lambda^*(k-d)$ (根据定理1)
    • $\ge c(P^*_d) + (d-k)\lambda^* + \lambda^*(k-d)$ (根据$\lambda^*$的取值范围)
    • $= c(P^*_d)$

定理2 证毕，这里说明给定的$d$, 可以找到 $\lambda^\in \mathbb{Z}$ 使得 存在长度为$d$的最小贡献的路径 刚好能取到表达式的min 且$=c(P^_d)$

定理3 $\displaystyle \min _ {P \in \mathcal{P}, \lVert P \rVert = d} c(P) = \max _ {\lambda \in \mathbb{Z}} \min _ {P \in \mathcal{P}} (c(P) + \lambda (\lVert P \rVert - d))$

首先根据定理2有 给定$d$ ，能找到 $\lambda^*$

$\displaystyle \min_{P\in\mathcal{P},||P||=d}c(P)$

$= c(P^*_d)$

$= c(P^*_d) + \lambda^*(d-d)$

$= c(P^*_d) + \lambda^*(||P^*_d||-d)$

$\displaystyle \le \min_{P\in\mathcal{P}}(c(P)+\lambda^*(||P||-d)))$, 根据定理2, $P^*d$是让这个表达式最小的$P$
$\displaystyle \le \max{\lambda\in \mathbb{Z}}\min_{P\in\mathcal{P}}(c(P)+\lambda(||P||-d)))$, 根据 $X \le \max(X,\cdots,)$

而 最上面有$\displaystyle \min_{P\in \mathcal{P},||P||=d}c(P) \ge \max_{\lambda\in\mathbb{Z}}\min_{P\in\mathcal{P}}(c(P)+\lambda(||P||-d))$

夹逼一下 所以是等于

至此定理3说明了， 通过 拉格朗日增加lambda项的方法，可以用来计算$\displaystyle c(P^*d) = \max{\lambda\in\mathbb{Z}}\min_{P\in\mathcal{P}}(c(P)+\lambda(||P||-d))$

对于 $\displaystyle L(\lambda) = \min_{P\in\mathcal{P}}(c(P)+\lambda(||P||-d))$ 实际是一次函数族的$\min$在点$\lambda$的值

而一次函数族的min 是一个上凸函数, 所以$c(P^*_d)$可以用三分搜索来计算

剩下的问题就是给定$\lambda$如何快速计算出$L(\lambda)$

$\displaystyle L(\lambda) = \min_{P\in\mathcal{P}}(c(P)+\lambda(||P||-d))$

$\displaystyle = \min_{P\in\mathcal{P}}(c(P)+\lambda||P||-\lambda d)$

$\displaystyle = -\lambda d + \min_{P\in\mathcal{P}}(c(P)+\lambda||P||)$

后面部分 实际上就是 所有路径的权重增加$\lambda$,去做最短路计算,而新图也满足Monge性质, 可以用 LARSCH algorithm(https://noshi91.hatenablog.com/entry/2023/02/18/005856) https://codeforces.com/blog/entry/110844

以及延伸还有 SMAWK algorithm

回到原题目，其实我们只需要引理1即可

下面问题是对于 下凸函数$d$ 找$K,d(K)$使得$d(K) \le X$

Alien DP可能需要$O(N \log^2 X \log N)$ 可能会TLE

同样注意到 既然是下凸，还可以用三分搜索

令$F(x)$ 为 $(i,d(i)-X),i=1\cdots N$ 点 构成的下凸函数

$D$ 显然是$y=F(x)$和$y=0$的交点, 向整数rounded up(因为F单调递减)

$G(p)$ 在Alien DP中 每个操作代价为p的最大代价(因为 alien dp就是 二分斜率k 找最小截距 $y_0= F(x)-kx$, 所以对于给定k, alien dp 输出的是 (p,G(p) = F(p)-kp)

$D = \lceil \max_p (\frac{G(p)}{p}) \rceil$, 中间的也是下凸函数，因此也D可以三分找到

const int LG=30; // 这里还有一个性质是如果A>=2,那么长度len的 >= 2^{len-1},而上限又是X <= 1e8, 所以一组的最大长度就有了限制

代码

https://atcoder.jp/contests/abc305/submissions/43061175

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
const int PWR=30; // 2^{len-1} <= X <= 1e8
const ll INF=3'00000'0000'0000;//>= 2e5*1e8 + 1e8,还要满足1e5*inf+1e8<=MAX_I64 乘法不越界
ll w[200010][PWR]; // w[start 0-index][length=r-l]
int n;
array<ll,2> solve(ll k){ // solve[k斜率] = {d,G(d)=max(dp[d] = cost[d] - k * d)} 划分成d段
  vector<array<ll,2> > dp(n+1,{INF,0}); // 1-index, {alien trick下的DP, 多少段 * -1}
  dp[0]={0,0};
  rep(i,0,n) rep(len,0,PWR) {
    int j=i+1+len;
    if(j > n) break;
    // 这里主要是处理连续的一段k相等, 那么这一段返回y最小的，也就是x最大，所以段数最大的
    dp[j] = min(dp[j], {dp[i][0]+w[i][len]-k, dp[i][1] - 1});
  }
  return {-dp[n][1], dp[n][0]+(-dp[n][1])*k};
}

int main(){
  n=read();
  int X=read();
  ll S = 0;
  vector<ll> A,B; // 0-index
  rep(i,0,n){
    ll a=read();
    ll b=read();
    if(a>1) {
      A.push_back(a);
      B.push_back(b);
    } else { // A == 1
      X-=b; // 放在区间的最后贡献只有b
      S+=b;
    }
  };
  n=A.size();
  if(!n) return printf("1 %lld\n",S)*0;
  auto cmp=[&](ll i,ll j){return (A[j]-1)*B[i]<(A[i]-1)*B[j];}; // 同区间内性质
  rep(l,0,n) {
    vector<int>idx(PWR);
    iota(begin(idx),end(idx),l);
    rep(len,0,PWR) if(l+len<n){ // 计算所有可能贡献的区间的w, O(n log X log X)
      per(i,1,len+1)if(cmp(idx[i],idx[i-1]))swap(idx[i],idx[i-1]);else break;//暴力冒泡排序
      rep(i,0,len+1) w[l][len]=min(w[l][len]*A[idx[i]]+B[idx[i]],INF); // 暴力计算cost
    }
  }
  ll l=-X-1,r=0; // l might ok(对应1个区间), r ok(对应分成N个), wqs 二分斜率, 截距 = y(x) - kx
  while(r-l > 1) { // log X
    ll mid=(l+r)/2;
    (solve(mid)[1] <= X ? r : l) = mid;
  }
  auto [seg,cost]=solve(r);
  // 注意这里可能连续 [? ... seg] 斜率(<0)都相等, f(?) > X，而在中间某处也满足f() <= X
  ll dx = min(seg-1,(X-cost)/(-r));
  printf("%lld %lld\n",seg - dx, cost + dx * (-r) + S);
  return 0;
}

总结

Ex

自然的和题解一样考虑了子问题

去掉A=1感觉也很有用，去掉后转移的长度就被限制到log X级别了

去考虑 相邻区间的划分了，没有去考虑说一个集合与子集 加入同样元素的变化贡献

这题 现场还有8个大佬做出来了？？？

（顺便说一句，这个 DP 源自 IOI（国际信息学奥林匹克）问题“Aliens”，所以更精确地称为“Aliens DP”可能更合适。根据上下文的不同，它也被称为“wqs 二分搜索”或“Lagrange 松弛”。）

abc218H 里首次学过wqs二分，这是第二次见到

顺便 这题 让我学了一下没见过的 四边形不等式 优化 DP

然后是 四边形不等式 在 指定边数的相关性质

然后实现起来比较怪的是，因为ax+b 很容易overflow, 而去取min 感觉会影响 凸性，而且这个INF似乎选起来总觉得各种别扭，而 关键点 就是 在当前指定斜率k下是否有(max - k d)超过 1e8, kd可以达到 1e8 2e5 = 2e13, 所以max 要大于 2e13+1e8 的去放置才行,

参考

官方题解

wikipedia Submodular_set_function

https://noshi91.github.io/algorithm-encyclopedia/d-edge-shortest-path-monge

oi wiki 四边形不等式优化