某岛

… : "…アッカリ~ン . .. . " .. .
November 13, 2022

ICPC World Final 2021

传送门

感觉今年题目貌似比 去年 简单,是我的错觉吗?(反正几何题大家都不会去开的)。
还是按照我认为的难度排序。。。

Problem H. Prehistoric Programs

贪心乱搞。

Problem A. Crystal Crosswind

我们需要找出必须是 ‘#’ 的点和必须是 ‘.’ 的点,剩下的可以随便填。
考察每组 wind 能够给出的信息:
(1): 首先对于其中的每组 (x, y) boundary,(x, y) 必然填 ‘#’,且 (x – wx, y – wy) 必然填 ‘.’。
(2): 除此之外,对于每个不在 boundary 的点 (x, y),也是能给出一定信息的(风大概还有个 z 轴从上向下吹的。。),要么 (x, y) 是 ‘.’ 要么 (x, y) 是 ‘#’ 且 (w – wx, y – wy) 也为 ‘#’。

其实就是 floodfill … 具体实现的时候,对于第一问,先假设所有点都是 ‘.’,然后根据 boundary 信息给出初始的 ‘#’,然后再对于每一个新的 ‘#’,用第二个条件去做 floodfill 填出其它的 ‘#’。
第二问的做法也类似,记得还要考虑边界外的 ‘.’。

Problem L. Where Am I?

因为我们要求和,所以只能暴力 bfs(),就是和前几天 CF 的那个题差不多,开两个队列来回倒腾,把所有源点弄成一个集合塞进队列里,然后每次移动一步,边移动边分拆集合,直到集合中只有 1 个元素,复杂度 O(n4)。
考虑到标记的规模只有 O(n),所以另一种做法是,我们预处理出每个点,到每个标记的距离,对这些距离按照字典序排序,就可以得到最早被分割的时间(结构类似后缀树组),复杂度 O(n3logn)。

Problem I. Spider Walk

I 题开始题目读错了。。以为是可以花费 1 的代价修 bridge,然后求单源最短路。。。但是实际上对于每一个弦(bridge)。。。只要遇到了,就是必须经过的。。。
那最后就是在这个东西上面 dp 。。。dp 的过程相当于,从远到近,每次加一些弦。。然后用这些弦去做松弛。。。每添加一条边,实际上是交换这两个点的状态,然后再分别向左和向右一路扫下去。。

2 3 3 2 1 0 1
2 3 2 1 0 1 1
1 2 2 1 0 1 2
1 2 1 1 0 1 2
2 1 1 1 0 1 2

以样例 1 来说的话。。dp 状态是这样。。考察第一条边加入之后,虽然交换了 dp[4], dp[5] 的值,但是 dp[6] 依然等于 1,因为我们再后续添加边时,可以决定添加边的顺序。。。
所以每个状态在任意时刻,除了交换的时候,dp 值不会变劣,确实符合 ”松弛“ 的一般定义。。。
最后只要动态离散化压缩 dp 状态即可。。。

Problem B. Dungeon Crawler

正解要倍增祖先 + dp,感觉非常难写。。。但是这个题可以 O(nq) 搞过去囧(想不到吧。。。
不过去年的 B 题都能 O(n2) 爆过去囧,这个当然也不算什么。。。。

Problem C. Fair Division

初始有 m 价值的金子,n 个海盗围成一圈,每次当前金子的 p/q 留给自己,剩余的给下一个人,这个过程将无限进行下去。
问是否能找到合法的 p, q 使得每个海盗获得金子的极限是整数(中间可以是分数)。。。

貌似很久以前 GCJ 出过一次海盗分金。。。这个题看起来推理过程要简单一些。。。
基本思想是先列出每个海盗分得黄金的等式,用简单的数论知识找到判别式,最后再用一些代数技巧估计 q 的上界,暴力枚举(或许,你也可以跳过这个步骤。。直接卡时)。

$$\begin{equation}
\begin{split}
& mf\sum_{i=0}^\infty r^i \newline
& r = (1 – f)^n \newline
& f = \frac{p}{q} \newline
\end{split}
\end{equation}$$

$$\begin{equation}
\begin{split}
mf\sum_{i=0}^\infty r^i & = \frac{mf}{1-r} \
& = \frac{mf}{1-(1-\frac{p}{q})^n} \
& = \frac{mf}{1-(\frac{q-p}{q})^n} \
& = \frac{mf}{(\frac{q^n-(q-p)^n}{q^n})} \
& = \frac{mfq^n}{q^n-(q-p)^n} \
& = \frac{mpq^{n-1}}{q^n-(q-p)^n} \
& = \frac{mpq^{n-1}}{q^n- \sum_{i=0}^{n}q^i(-p)^{n-i}\binom{n}{i}} \
& = \frac{mpq^{n-1}}{\sum_{i=0}^{n-1}q^i(-p)^{n-i}\binom{n}{i}} \
& = \frac{mq^{n-1}}{-\sum_{i=0}^{n-1}q^i(-p)^{n-1-i}\binom{n}{i}}
\end{split}
\end{equation}$$

上面的 q^{n-1} 和分母是互素的,因此在判定整除时可以直接忽略。
具体来说,如果 a, b 互素,那么 a^n – b^n 与 a 和 b 都互素。证明可以反证法,假设存在素因子,推出 a 和 b 不互素即可。。。
利用这个结论,不仅可以简化判别式,还可以发现任意考察哪个海盗都一样。。。。

上式还可以继续二项式展开。。。

$$\begin{equation}
\begin{split}
\frac{mp}{q^n-(q-p)^n} & = \frac{mp}{q^n- \sum_{i=0}^{n}q^i(-p)^{n-i}\binom{n}{i}} \
& = \frac{mp}{-\sum_{i=0}^{n-1}q^i(-p)^{n-i}\binom{n}{i}} \
& = \frac{m}{\sum_{i=0}^{n-1}q^i(-p)^{n-1-i}\binom{n}{i}}
\end{split}
\end{equation}$$

我们发现上面的 p 因子也可以消去。。。
进一步我们可以使用不等式对上式进行放缩,或者直接把 n 最小的情况往里面代入,得到 q 的上界即可。
其实我觉得还是挺难的囧。

Problem G. Mosaic Browsing

算法导论告诉我们,Rabin Karp 算法可以非常容易的将字符串匹配推广到矩形上(其实就是 Hash 乱搞),但是我们很快发现此题真正要处理的难点是通配符。
学习了例题之后我们发现只要用 FFT 就可以有效的解决这个问题了~!而且只有模式串有通配符。。判别式还要更简单一些。

似乎还有一种高级做法。。。我不会
https://twitter.com/heno_code/status/1590682021369884672

Problem E.

Problem F. Islands from the Sky

显然可以二分答案,更简单的做法是,对于每一条航线,去更新所有多边形的最小可行角度,最后再取最大值即可。
只需要对多边形的每个顶点做到航线的投影,然后反正切函数即可。

Problem K. Take On Meme

最后还剩两道几何题。。。Minkowski Addition + 凸包乱搞即可。

Problem D. Guardians of the Gallery

OMG,我们先要搞出多边形内部可以看见目标点的区域,是个凸多边形,然后只要求点到这个凸多边形的距离即可。