KEYENCE Programming Contest 2021 题解

Froggy · 2021-01-17 14:27:13 · 个人记录

KEYENCE Programming Contest 2021

A - Two Sequences 2

逗比题。

code

B - Mex Boxes

逗比题\times 2。

code

C - Robot on Grid

设 dp_{i,j} 表示所有 3^{nm-k} 个方案里从 (1,1) 到 (i,j) 的方案数之和。

初始状态： dp_{1,1}=3^{nm-k}。

转移很 naive。（具体见代码）

code

D - Choosing Up Sides

方便起见，设 a 和 b 分别表示题面中所述的 n 和 m，题解中的 n 和 m 分别对应题面中的 N 和 M。

手玩出 n=2：

AABB
ABAB
ABBA

盲猜一波答案等于 2^{n}-1。

证明：

必要性：

每轮属于两个不同组别的数对增加 4^{n-1} 个。一共进行 a+b 轮，所以 (a+b)4^{n-1}=b\begin{pmatrix}2^n\\2\end{pmatrix}

解得 a:b=2^{n-1}-1:2^{n-1}。

这样轮数一定是 2^n-1 的倍数。

充分性：

构造就要看观察力了。可以再玩出 n=3 进行观察。

对于第 i 轮第 j 个人（编号 0\sim 2^{n}-1），如果 i\ \mathrm{and}\ j 二进制下 1 的个数为偶数就让他属于 A 队，否则让他属于 B 队。容易证明这样构造一定合法。

code

E - Greedy Ant

转化一下规则： Snuke 每回合只能吃掉 a_l 和 a_r 中的一个 （a_l 和 a_r 分别是目前 Ant 左边/右边最近的没吃过的 a_i）或者可以选择不吃并把机会留到之后（即之后 Snuke 可能会连着吃）。这样转化显然与原问题等价。

枚举起点后，显然有个 \mathcal{O}(n^3) 的 dp：设 dp_{l,r,k} 表示 (l,r) 区间中的东西都吃了，下一步将要吃 a_l 或者 a_r，然后 Snuke 已经吃了 k 次获得的最大值。

下一步 Snuke 能接着吃当且仅当 k<r-l-k，即 2k<r-l。

由于要枚举起点，所以直接做是 \mathcal{O}(n^4) 的。

那么不妨倒着做。dp_{l,r,k} 的意义修改为 (l,r) 区间中东西都还没吃，Snuke 能获得的最大值。起点在 i 和 i+1 之间的答案就是 dp_{i,i+1,0}，初始状态为 dp_{0,n+1,\frac{n+1}{2}}=0，这样一遍 dp 就能完成。

时间复杂度：\mathcal{O}(n^3)。

code

F - Keyence Repetition

先考虑一个别的字符串，比如 abcxyz（每种字符出现最多一次）

设 f_i 表示 t_i 在某个循环节中的位置，对于上面这个字符串来说，f_i 都已经固定。

设 g_{i}（1\leq i\leq |t|）表示 |t| 中第 i 个字符在原串的第几个循环节中。