Codeforces Global Round 25

發表於 2024-04-06 更新於 2024-10-23 分類於 Codeforces ， Div1+2 Disqus：文章字數： 3k 所需閱讀時間 ≈ 10 分鐘

G(概率论)H(二分,树)I(TODO)

https://codeforces.com/contest/1951

G Clacking Balls(2s,256mb)

1~m篮子顺时针环

n个球，第i个在篮子ai中，每个篮子至多1个球

alice 可以进行1s操作

[1,n]等概率选i
如果球已经不存在，则跳过（依然耗时）
如果球存在，则沿着把球顺时针移动一个篮子，（如果目标篮子有球，把目标篮子中原来的球抛弃）

直到只剩下一个球停止，求操作时间的期望值 mod 1e9+7

n 3e5

n,m 1e9

我的思路

不能说没有想法，只能说一点想法也没有

如果一个球消失，那么说明有前面的球超过了它，换个角度如果球i移动导致球j消失，也就是i走到j的位置，那么换成i消失是等价的后续，不影响概率

所以转换了题意的第三条（谁移动谁消失）以后

如果说最后剩下的是第i个球，那么这个球没有触碰下一个球，而前面的所有球触碰了后一个球

所以是个min/max 容斥+期望吗？

计算每个球的消失(触碰后面球)的期望次数，再min-max 容斥掉?

感觉也不对

再换个角度，如果i留下

1	[i-1 ................i] .....

没啥想法，总的来说，显然直接状态描述肯定不行的，不论是点坐标还是距离

那么要么就是孤立每个间隔的期望什么的，要么就是孤立的什么点期望，总之需要一个办法把其中关联的东西拆掉，

而且不只如此，还有环

然后就是考虑简化的问题，同样是环，但是只有两个点

那么 Exp(state) = Exp(点的距离)

然而转化构成了一个转化矩阵

$A\lambda=\lambda$的形式，已知$A$要求$\lambda$

另一个是展开环到无限的数轴，指定目标点，那么得到每个点的移动方案数？

题解

这题的发想来自于一个4年前的 CF ROUND 641 Div1 D的一个戴江齐的评论

说白了就是

$E(state)=1+\sum_{newstate} p_{newstate}E(newstate)$

然后“猜想，数学直觉”，认为$E(state)=\sum_i f(a_i)$, 而这个$f$是任何一个满足上面 state转换的即可

这样找出任何一个满足上面转换的$f$以后就只需要

$ans = E(初始state)-E(结束state)=(\sum_i f(a_i))-(\sum_i f(end_i))$

剩余$k$个球时

令 $S=(d_1,\cdots,d_k)$ 为状态，记录所有点之家你的间隔

$D=\sum_{i} d_i$

对于第$i$个长度$\frac{1}{n}$ 概率, $d_i+=1,d_{(i+1)\mod k}-=1$, 如果后一个变为$0$ 从状态中删除这一项，把新状态记作$S_{+\lbrace i\rbrace}$

有$1-\frac{k}{n}$ 什么都不发生，（选中未被删除的球)

终点状态是 $S_{end} = (D)$

$E(S_{end})=0$, // 这里也可以不是0,换成一个新的函数H而不是期望，这样的话只需要$ans = H(S_{start})-H(S_{end})$

$E(S)=1+\frac{1}{n}\sum_{i=1}^k E(S_{+\lbrace i \rbrace})+(1-\frac{k}{n})E(S)$

整理得到

$kE(S)=n+\sum_{i=1}^k E(S_{+\lbrace i \rbrace})$

$n=\sum_{i=1}^k(E(S)-E(S_{+\lbrace i\rbrace}))$

上代江齐的想法

如果存在 $E(S)=C+\sum_{i=1}^k\sum_{x=0}^{d_i} g(x)$

$n=\sum_{i=1}^k(E(S)-E(S_{+\lbrace i\rbrace}))$

$=\sum_{i=1}^k(g(d_{(i\mod k)+1})-g(d_i+1))$, 因为操作{i} 其余的都对应消除掉了，只多剩下$g(d_i+1)$和$g(d_{(i\mod k)+1})$

$=\sum_{i=1}^k(g(d_i)-g(d_i+1))$, 整理$i$

特别的，我们希望$(1,1,1) \to (1,2,0) \to (1,2)$时

希望 $E((1,2,0))=E((1,2))$

而左边多一个$g(0)$ 所以，最好$g(0)=0$

令 $g(d_i)-g(d_i+1) = \frac{n}{D}d_i$, 则满足上式$n=\sum_{i=1}^{k}(g(d_i)-g(d_i+1))$

$g(x)=g(x-1)-\frac{n}{D}(x-1)$

$g(x)=-\frac{n}{D}(\sum_{i=1}^{x-1} i)=-\frac{n}{D}\binom{x}{2}$

$E(S)=C+\sum_{i=1}^k\sum_{x=0}^{d_i} (-\frac{n}{D}\binom{x}{2})=C-\frac{n}{D}\sum_{i=1}^k\binom{d_i+1}{3}$

为了满足$E(S_{end}) = 0$

$0=C-\frac{n}{D} \binom{D+1}{3}$

$ans=E(S_{start})=\frac{n}{D}\binom{D+1}{3}-\frac{n}{D}\sum_{i=1}^k\binom{d_i+1}{3}$

H Thanos Snap(3s,512mb)

给定 $a[2^k]$ 初始是 $[1,2^k]$的一个排列

一个$t\in[1,k]$ 被展示给A和B

score = 在t轮后max(a)

每一轮

A：不操作或选a中两个不同的元素交换, 希望score尽量大

B：a删除左半或右半，希望score尽量小

1 2	for t=1..k print(score for f(a,t))

$k \le 20$

我的思路

考虑剩余轮数会怎么操作,g(a,剩余轮次)

如果剩余0轮，都不操作, g(a,0)=max(a)

如果剩余1轮，那么B一定会删除最大的数所在的一半，那么A的任务就是次大的数要和最大的不在同一半即可，g(a,1)=次大(a)=max(a,2)

用max(a,j) 表示a中第j大的

那么如果剩余2轮，那么B 一定是删除左右中 max(a_left,2),max(a_right,2)更大的一侧，那么对于A来说，就是要让 max(a_half,2) 小的尽量大

然而这出现了分叉，无法直接判断是a的第多少大的了

1234 5678
那么1次移动 max(左,2) 最大只能是4,而右边 max(右,2) >= 5,

最有的期望是 max(a,4), 但上述的方法无法达到，而注意到 只要最大的4个不同时在一侧，那么 要么最大四个的分布 只有 1-3,2-2,3-1，都可以通过1次或0次移动让结果是max(a,4)

所以结果是 min(max(a_left),max(a_right),max(a,4))

感觉无法继续更多的剩余轮次，因为这里的状态很复杂了

另一个角度想就是如果最优为$x$, 我们能否让结果 $\ge v$, 显然在不改变Alice和bob的决策情况下，这是单调的可以二分

那么以$v$为分界点，Alice和Bob的决策在新的视角下会怎样

把 $\ge v$的全换成1,$< v$的全换成0

那么, 原来的“最优操作”实际上，Alice和Bob博弈下来就是留下1的个数，而分界点$x-1,x$ 上分别是留下1个1,和完全不留1

所以原题目变化为（总感觉数学上没有完全证明这两个等价，但是感觉上是这样的？）

Alice要尽可能保留1,

Bob要尽可能移除1

但这也注意到这似乎没有局部贪心？

11111111 00000000 10101010 1010000
8个1     0个1      4个1      2个1

如果这时候，Alice选择了左右平衡 两边都变成7个1
那么 Bob, 会选左侧
11111111 00000000

那么Alice最多让右侧有1个1
Bob会留下
100000000

alice不论怎么选
Bob会得到
0000

而3次操作来说，

11111111 00000000 10101010 1010000
8个1     0个1      4个1      2个1

alice这样操作第一次
11111110 00001000 10101010 1010000
Bob 如果留右侧，
	则alice 可以把右侧变为 10101000 10101000
	Bob => 10101000
	alice 不操作
	Bob => 1000

Bob 如果留左侧
	则 alice => 11101110 10001000
	Bob => 10001000
	alice 不操作
	Bob => 1000

所以3次操作来说已经说明了，Alice如果只是简单的平衡左右1的个数的话，显然是没有局部最优性的

但如果只有1次操作，那么alice就应该直接平衡成左右都是7个了

这里说明了最终次数t也影响他们的决策

没啥想法，一个想法是直接暴力

也就是 f(状态，次数)=true/false(能否留下1)，而这里状态可能需要一个长度幂次标识

所以大概是 O(k^2 2^k)的状态

然后转移的话最多 (k/2)^2 （把1移动到0）种

这样感觉就TLE了

如果只看状态的话$k^2 2^k$ 似乎还可以卡一卡，特别是这里长度标识应该是标不满的

$\sum_{i=1}^{20} i 2^i = 3984,5890$

所以如果转移能优化效率那就更好了

f(s)=f(s_left+s_right)
= for 移动方案
	or (f(方案s_left) and f(方案s_right))
= (for 左向右移动) or (for 右向左移动) or (for 左不动右内部) or (for 右不动左内部移动)

因为 括号内 是and，外部是or,所以 需要两侧都是true 才能对外部贡献

(for 左向右移动) 和 (for 左不动右内部) 都需要 f(s_left) = true, 因为如果原来左侧不动都没有方案，那么左侧少1个肯定更不行

if f(s_left):
	if f(s_right):
		res = true;
		break;
	ok_left_sub1 = for f(s_left 移出1个) 存在true
	ok_right_add1 = for f(s_right 移入1个) 存在true
	if ok_left_sub1 and ok_right_add1:
		res = true;
		break
	if not ok_right_add1:
		// 不可能 因为 增加1个都不行，那么调整位置肯定也不行
	else: 
		// 这种就是 左侧不动可以，少1个不行，右侧直接不行，右侧增加1个可以，不知道调整位置是否可以
		// 然而这种状态数可以达到 (n/4)^2 = 25 个左右
		for s_right调整位置 存在true

右侧对称同理

感觉这样的话，不知道是TLE还是卡着时间线能过？

再整理

if f(s_left) and f(s_right): 都不动就可以
	true
	break

if not f(s_left) and not f(s_right): 不动都不行，然而要么一侧不动要么一侧少一个始终不行
	false
	break

// 那么无非是
//   1. 可以的 向不可以的 转移1个， 两边都可以 存在f(可以-1)==true and f(不可以+1) == true
//   2. 存在 f(不可以+1) == true
//          且存在 f(不可以 内部调整1) == true

题解

一样的二分转化

只是变成了 t+1层的树，Bob从根向下走，而Alice可以交换数组中两个位置的值

叶子节点对应长度$2^{n-t}$的数组区间
Alice要做的就是让最后到达的叶子对应的区间里有1
Bob就是要让对应区间里没有1（记作 deficient 叶子）
那么有多于1个1的leaf可以贡献额外的1
如果在走到节点p时的操作，在p的任意祖先节点也可以操作，
- 这个观察，让我们考虑从下向上思考
- 记录每个节点对应的 deficient 叶子个数和可以借用的额外1的个数
- 那么如果当前位置的 (deficient,可借用) 都非0,则完成1次转移，并把剩余的向上传递
- 那么 alice 需要在根部时为deficient=0 才能获胜

总结

VP了这场（5198分大概2172的表现（如果实际打会掉分）），前面题卡了有点久，还WA了一发D

A(7min)

B(19min)

C(38min)

D(51min), WA+1

E(32min)

F(62min): 超时29min 自己做出来了

戴江齐大佬的这个数学直觉法，简单暴力有效啊！！

像待定系数法的感觉，又很帅，而且这里拆g的时候拆成从0到di的和也很有意思，这样变成2次类和的话，转换时不会剩余4项而只会剩余2项

我也把 round 641 D的题解文字补了

一样的二分转化，但是后续的树型没建立出来，在想记忆化DP，

而这个树型转化，其实核心还是引出了倒着想的（自下向上的想法）

I: TODO

官方题解

对我来说，H看上去比G简单，二分很自然，这个树型转化自己也应该要能想到的。哎。

不过H的收获很大，感觉概率论如果有这个方法的话，似乎能搞的题增多了不少，但其数学原理感觉还是不透彻，因为还是有可能制造出的表达式虽然满足但是过于复杂产生过拟合一样的效果吗？？？