Atcoder abc313

發表於 更新於 分類於 ， Disqus： 文章字數： 3k 所需閱讀時間 ≈ 10 分鐘
F(概率论,bitdp)G(floor_sum)Ex(数数)

https://atcoder.jp/contests/abc313

F - Flip Machines

n张卡，正面ai,背面bi，初始都是正面

m个机器，对应卡xj,yj，！！xj可能等于yj

如果一个机器启动 则1/2几率 翻转卡xj,否则翻转卡yj

启动机器的集合任意选择

问 所有的 启动机器的集合 的方案中 卡的和的期望值最大是多少

n 40

ai,bi [1,1e4]
m 1e5

2s

1024mb

我的思路

显然是个概率论的题

n 比较小，m中等，ai,bi中等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
卡 a1 a2 a3

m组
[1,2]
[1,3]

第一次翻转
b1 a2 a3
a1 b2 a3

第二次翻转
a1 a2 a3
b1 a2 b3
b1 b2 a3
a1 b2 b3

从频次的角度来看， 如果涉及到翻转，那么该位置的期望贡献就是 (a[i]+b[i])/2

如果不涉及翻转 那么期望贡献就是 a[i]

所以选取的集合 就算再多，也只和被激活的那些有关，和一个位置被选了几次无关

所以问题可以变为，基础 = sum ai,

di = (b[i]-a[i])/2

有一堆激活的pair可以任意选，

问 最大 di和为多少

把di 按照正(>=0),负(<0)分类

如果有 (+,+)的di pair则一定选， 如果有(-,-)一定不选

那么剩下的就是 (+,-)的

而这类如果 其中的+已经选了 则一定不选

所以变成了, 未被选的+,所有- 和很多(+,-)的问题

那么显然 至少一侧的个数 <= n/2 = 20

这就很像bitset了

如果 所有-的个数 <= n/2 那最简单, 就是贪心选掉所有(+,-)有-被选的正的里面的

如果 所有+的个数 <= n/2???

1
2
3
4
(a0 10,b0 -5)
(a1 10,b0 -5)
(a0 10,b1 -4) 对于 单个来说最小， 但是 上面都选b0 比 选两个b1,b2更优
(a1 10,b2 -4)

只能说 最终被选的 -的个数肯定 <= n/2, 因为每个(+,-) 最多选一次

n-正 个中 选 <=正的方案数？ 这有多大？

正=20时 2^20

正=19时 $2^{21}-\binom{21}{21}-\binom{21}{20}$

正=18时 $2^{22}-\binom{22}{22}-\binom{22}{21}-\binom{22}{20}-\binom{22}{19}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def binom(n,m):
    s = 1
    for i in range(1,m+1):
        s *= (n+1-i)
        s //= i
    return s

def f(pos):
    neg = 40 - pos
    r = 2**neg
    for i in range(pos+1,neg+1):
        r -= binom(neg,i)
    print(pos, r)

for i in range(1,21):
    f(i)

看输出 感觉 还是2s过不了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1 40  
2 742  
3 8474  
4 66712  
5 384168  
6 1676116  
7 5663890  
8 15033173  
9 31621024  
10 53009102  
11 71116846  
12 76717268  
13 67108864  
14 48412432  
15 29703676  
16 16241061  
17 8344056  
18 4192510  
19 2097130  
20 1048576

题解

几乎一样的处理题意

也是 如果暴力 枚举 更劣的点， 那么贪心连接边 则 O(n 2^|劣|)

然后就是 我上面自己没想到的 优势一半的 个数<=n/2时

处理方式是 bitdp

dp[i][mask] = 前i个劣势状态的所有方案中，优势选择的情况为mask的最优代价和

然后我漏考虑了xj=yj, 这种的话 就是100% 选择更优的就行了

G - Redistribution of Piles

a[n] \in[0,1e9]

n 2e5

每次二选一，做任意次

  • 所有石头 > 1，减去1个, bag+=对应的值
  • bag-=N, 所有+=1

问可以得到的数组的方案数 mod 998244353

2s

1024mb

我的思路

不知道怎么牵连这个变化值进来

比如我想把一个地方垒得很高，

那么先清空，然后不断所有+1

然后把不是目标位置的都清除

再所有+1, 如此反复直到 挖完后bag中个数< N

然后对于单点来说， 变小总是可以的

变大都需要一次全+1

如果把它们按照目标从小到大排列

那么每次除了最大的全部删除，所有+1，这样直到最大的达到目标

然后问题到次大的，还是除了次大了 前面的所有删除，最大的-1, 然后所有加1

所以其实像是在 最大的完成时 是 (n-1) + 最大 <= all

次大的是 (n-1) + 次大 <= all - (最大-1)

所以从大到小排 需要 (n-1) + 目标 <= all - sum (比他大 - 1)

比它小的个数 + 目标 <= all - sum 比他大

这里 比他大 如果大小相等 则比较index

那么问题是

  • 这样的方案数如何算
  • 有没有一种方案 是这样的操作无法达到的

想法是

  • 如果 所有放完以后剩余remain >= n-1,那么所有位置随便放，就是个球插板法
  • 如果所有放完以后剩余remain < n-1, 似乎只需要 0的个数 <= remain 即可，这样的状态都可达
  • 这样操作无法达到的，显然也属于 剩余的 < n-1里的，因为 >= n-1剩余的 所有状态都可达，并且0的个数 > remain,
1
2
3
4
5
0 0 0 0 1 1 1 1 2 2 2 2 ...

remain < n-1

0 个数 <= remain

如何处理 remain < 0 的个数 且 remain < n-1

如果执行过一次所有+1，那么每变成一个0,至少remain+1, 所以这种状态一定是 未执行过所有+1

所以 这种状态就是直接减

dp[i][j][k] = 前i个有j个0, k个remain是否能达成

然而这$O(N^3)$的样子

其实同理，如果在指定0的时候 是从正的下降，那0个数增长是大于等于 remain的，所以一定有一些0是来自原本的0，那么对于下降的来说就是使用一次初始的0，所以可以优化成

所以dp[i][z] = 前i个剩余未使用0的方案数

dp[i][z] = dp[i-1][z] + dp[i-1][z+1] + dp[i-1][z+2] .. , 一个是转移的值 大于等于增长+inc, 其次 当 转移值 用尽 a[i],只需要+(a[i]-1)

然而还是$O(N^2)$, 转移倍率复杂度可以用区间和 优化成O(1)

这里可以拆的是， 指定一些非0的位置为0, 让dp转移始终 +增长量

问题变成，有n-(所有变成0)个 a[i]-1 的球 的盒子 从中取不多于 count(zero) - sum(a[指定0]-1) > 0 个球的方案数

如何快速求？生成方程?

题解

读错题了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

读成 任意位置减去任意个了

那 这原题意就是 所有 -=1, bag+=count 或者， bag-=n, 所有+=1

那么第二个操作 显然是后置的， 否则 状态->操作2->操作1->状态

state -> k操作1 -> q操作2

满足 $\sum \min(k,a[i]) \ge q\cdot n$

$a[i]_{new} = a[i]-\min(k,a[i])+q$

然而这样的话 k的取值不会少

同样的观察，至少一个变成0以后，才会考虑使用q

$\min(a[i]) < k \le \max(a[i])$,随着k增加，$\sum \min(k,a[i])$ 有n段斜率

观察 最大的是 a[i]-k+q,而最小的是q,所以 不同的(k,q)对应不同的方案(满足上述限制)

1
2
3
4
5
6
f(k,q)
	for &ai in a:
		if ai >= k:
			ai -= k-q
		else:
			ai = q

感觉需要从n段斜率下手

1
2
3
4
5
6
7
8
ans += min(a[i])+1 只用操作1 且操作1 >=min(a[i])

// 操作1 > min(a[i])
total = 0
for k in min(a[i])+1...max(a[i])
	slope = currentslope()
	total += slope
	ans += total / n + 1

要转化也是

1
2
3
for slope in n-1..1:
	for k in range_k_from_slope(slope):
		ans += (base+k*slope)/n + 1

需要floor_sum即可(atcoder库里有, abc283也有floor_sum)

代码

https://atcoder.jp/contests/abc313/submissions/49534183

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
#include <bits/stdc++.h>
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;
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;}

// $\sum_{x=0}^n \lfloor \frac{ax+b}{c} \rfloor$
ll floor_sum(ll a,ll b,ll c,ll n){
  if(a==0) return (b/c)*(n+1);
  if(a >= c or b >= c) return n*(n+1)/2*(a/c) + (n+1)*(b/c) + floor_sum(a%c,b%c,c,n);
  ll m = (a*n+b)/c;
  return m*n - floor_sum(c,c-b-1,a,m-1);
}

int main() {
  ll N=read();
  vector<ll> A(N);
  for(ll&x : A) x=read();
  sort(begin(A), end(A));
  ll inbag = A[0] * N; // 减少和
  mint ans = A[0] + 1; // 减少次数 <= min(A)
  rep(i,1,N){ // 减少次数 > min(A), 减少次数 (A[i-1], A[i]]
    // for i in (L,R]: ans += (x*slope+base)/n+1
    ll L = A[i - 1];
    ll R = A[i];
    ll slope = N - i; // 每轮减少个数
    ll base = inbag - L * slope; // total = inbag + (x-L)*slope
    ans += floor_sum(slope, base, N, R);
    ans -= floor_sum(slope, base, N, L);
    ans += R - L;
    inbag += (R - L) * slope;
  }
  printf("%d\n",ans.val());
}

Ex - Group Photo

第一排a[n],第二排b[n+1],所有数字两两不同

每排内可以随意换位置

目标

1
2
3
a1 < b1
（a[i-1] or a[i]） < bi, for i\in[2,N]
an < b[n+1]

问 有多少第一排的所有重排列n!的方案mod 998244353，满足可以通过重排列第二排 来满足上述目标

n 5000

ai,bi 1e9

2s

1024mb

我的思路

题意简化就是每个bi要么大于ai,要么大于a[i-1]

这个or给我看傻了

如果是 没有这个or的情况，就是对应大于的话，那就是无脑的 的排序一一对应

而如果排序一一对应是可行的话，其实N!所有方案都可行

然后这里N给到5000的意思是要N^2吗

那对于一个给定的a[i]方案,如何判断它是否有对应的bi方案呢

那还是继承上面的贪心的想法，从最大的ai向下考虑，如果当前没有放置，则放置最大的bi到它对应位置？？？

然而似乎是不行的例如 这样也是一个方案

1
2
1 100 99 2
3 4  200 5   6

那么类似的，就是放置到它正下方或者+1的位置

不太行

那么就ai从小到大

对于最小的ai,需要bi,bi+1都比它大,而且一定取最小的两个bi

1
2
.........ai..........
.........bi b[i+1].....

而且关心的是bi是否合法,所以这两个bi就不用考虑了,剩下的 ai和 bi都是n-1个

1
2
[........]  [..........]
[........]    [..........]

那么次小的a[i-1] 一样的，如果是对应两个位置就是最小的两个bi,如果对应1个位置就是最小的1个bi

1
2
3
4
5
6
7
8
9
10
11
b = sorted(b)
checked = set()
for idx in list(sorted({a_i,i}).map(_=>_.i)):
	check = (idx, v)=>{
		if checked.has(idx): return true
		if(b.pop() < v) return false
		checked.insert(idx)
	};
	if not check(idx  , a[idx]): return false
	if not check(idx+1, a[idx]): return false
return true;

也就是 checkcount[i] = 2 - int(a[i-1] < a[i]) - int(a[i+1] < a[i])

然后 sorted(b) 按照 sorted(a)的checkcount每次检验对应大小

dp[i][cnt] = a的前i个，已经检验的b的个数为cnt

dp[i][cnt] = dp[i-1][cnt-0/cnt-1/cnt-2] ??? 转移条件呢

首先 cnt-2/-1/-0的发生需要满足bi和ai的大小关系

其次，注意到 当 -2时 意味着 ai中产生了一个不连通的新块(block+1)

-1时意味着某个块 增加了一个元素(block)

-0时意味着合并了两个块(block - 1)

由此得到 校验个数变化 = block变化+1

操作次数 x 校验个数变化 = 操作次数 x (block变化+1)

block个数 = 校验个 - 操作次数

ans = block个数=0

所以转移为

1
2
3
4
5
6
7
8
9
10
11
for i in 1..n : # 1-index a,b
	for cnt: # 校验个数
		block = cnt - i
		# 产生一个新块, block - 1 => block, 有block个间隙可以选
		if check(a[i], b[cnt+1]) and check(a[i],b[cnt+2]):
			dp[i][cnt] += dp[i-1][cnt-2] * block
		# 某个块左右扩展，
		if check(a[i], b[cnt+1]):
			dp[i][cnt] += dp[i-1][cnt-1] * block-1
		# 连接两个块 block + 1 => block
		dp[i][cnt] += dp[i-1][cnt] * block

答案

ans = dp[n][n+1]

似乎就过了

参考

https://atcoder.jp/contests/abc313/editorial

总结

F: 真不应该啊，都分析到那个地方了，最后的bitdp应该也很自然就能想到

G: 和F差不多啊，甚至需要floor_sum(第二次遇到)比F难，虽然是我读错题了艹，不过这两道题从难度上，自己都应该能过

Ex: 感觉甚至比F，G还简单，也没想很久

这期如果不考虑时间，应该自己能ak