去年的比赛拖到今年发了呢...
Atcoder Proving Contest
A. My Last ABC Problem (2000)
场上打表找规律找了半天
考虑如何处理单个询问。
显然连续相同字母可以缩起来（即不会在段内分割），设段数为 \(k\)。
对于一次操作 \([l,r]\)，显然 \([l,r]\) 内的段数不会减少，\([1,l)\) 及 \((r,n]\) 的段数也不会减少，减少的只有可能是 \(l-1,l\) 之间及 \(r,r+1\) 之间。每次至多减少 \(2\) 段，故答案有下界 \(\lceil \dfrac{k}{2} \rceil\)。
结论：当 \(k \geq 5\) 时，一定存在 \([l,r]\) 使得操作后减少 \(2\) 段。
证明：不妨设 \(S_2=A,S_3=B\)。
- 若 \(S_1=B\)，则取 \(l=r=2\)；
- 若 \(S_4=A\)，则取 \(l=r=3\)；
- 否则 \(S_1=S_4=C\)。
- 若 \(S_5=B\)，则取 \(l=r=4\)。
- 若 \(S_5=A\)，则取 \(l=2,r=4\)；
观察发现 \(k=3\) 时需要 \(1\) 或 \(2\) 次操作，\(k=4\) 时必须要 \(2\) 次操作。
于是当 \(k\) 为偶数时答案为 \(\dfrac{k}{2}\)，\(k\) 为奇数时答案为 \(\dfrac{k-1}{2}\) 或 \(\dfrac{k+1}{2}\)。
结论：当 \(S_1=S_k\) 时，答案为 \(\dfrac{k-1}{2}\)，否则为 \(\dfrac{k+1}{2}\)。
证明：容易发现在操作过程中 \(S_1\) 与 \(S_k\) 始终不变。故当 \(k\) 缩减到 \(3\) 时，若初始 \(S_1=S_k\) 则有答案 \(\dfrac{k-1}{2}\)；否则有下界 \(\dfrac{k+1}{2}\)，又由于任何最优策略必定会缩减为此情况，故这也是上界，证毕。
即答案为 \(\lfloor \dfrac{k+[S_1 \neq S_k]}{2} \rfloor\)。
对于多组询问，前缀和预处理即可。总时间复杂度 \(O(n+q)\)。
Code
B. Arrange Your Balls (1900)
B < A
设出现的颜色种类数为 \(k\)，记 \(S\) 表示题目中的相邻颜色对种类数。
首先可以给出一种 \(S=k\) 的构造：将相同颜色的球全放在一起。
结论：\(S \geq k-1\)。
证明：构建一个无向图，对于所有相邻颜色对 \((x,y)\)，连边 \((x,y)\)。显然该无向图是联通的，故（去重边后的）边数 \(S \geq k-1\)，证毕。
结论：当 \(n<2(k-1)\) 时，\(S > k-1\)。
证明：如果无向图（去重边后）是棵树，那么环上的顺序相当于图的一个欧拉回路，故所有点入度为偶数，可以归纳得到树上每条边对应的重边数量均为偶数，即每条重边至少出现 \(2\) 次。故 \(n \geq 2(k-1)\)，证毕。
事实上，当 \(n \geq 2(k-1)\) 时一定存在一组 \(S=k-1\) 的解，下面给出构造。
-
如果所有颜色都出现至少两次，就直接把所有颜色套起来。
-
先拿一个只出现一次的颜色定为第一个，断环为链，将指针设置为它后面的位置。
-
对于一种有 \(k \geq 2\) 个球的颜色，将 \(k\) 个球全部放在指针位置，再在前面的 \(k-2\) 个空隙中放入只出现一次的颜色，最后将指针设为最后一个空隙。
-
最后剩下一个球放入指针位置。
注意到有 \(k\) 个球的颜色会带来 \(k-2\) 个空隙（只出现一次的颜色则消耗 \(1\) 个空隙），上述过程中 \(\sum (k-2)=n-2(k-1) \geq 0\)，故方案合法。
总时间复杂度 \(O(n)\)。
Code
C. Guessing Permutation for as Long as Possible (2900)
结论：对于排列 \(\{P_i\}\) 和 \(k \in [1,\dfrac{n(n-1)}{2}]\)，\((A_k,B_k)\) 可以被跳过当且仅当存在 \(m \geq 2\) 和 \((A_{i_1},B_{i_1}),(A_{i_2},B_{i_2}),\cdots,(A_{i_t},B_{i_m})\) 使得 \(i_t \leq k,A_{i_1}=A_k,B_{i_m}=B_k,B_{i_t}=A_{i_{t+1}}\) 且 \(P_{A_{i_t}}<P_{B_{i_t}}\)（或者全部大于）。
证明：充分性显然，考虑证必要性。记 \(P_{A_k}=X,P_{B_k}=Y\)，不妨设 \(X<Y\)。考虑 \(A_k < r <B_k\) 使得 \(X<P_r<Y\)，记 \(P_r=Z\)。
若 \((X,Z)\) 与 \((Y,Z)\) 不能均问过（否则违背前提），不妨设没有问过 \((Y,Z)\)。则可以将位置介于 \((r,B_k)\) 的数中与 \(Z\) 通过连边联通的和 \(Z\) 一同移动到 \(Y\) 的右端，这样新的排列 \(P'\) 仍然合法。
重复这样的操作，最后得到的排列中 \(X\) 与 \(Y\) 间没有介于 \((X,Y)\) 的数。此时调换 \(X\) 与 \(Y\) 仍然合法，代表 \(P_{A_t}\) 与 \(P_{B_t}\) 的大小关系无法确定，证毕。
结论：排列 \(P\) 合法当前仅当对所有 \(k\) 上述条件在 \(m=2\) 时成立。
证明：考虑 \(m>2\) 的条件成立的情况。如果已经问过 \((A_{i_1},B_{i_2})\)，则将 \((A_{i_1},B_{i_2})\) 和 \((A_{i_2},B_{i_2})\) 缩成 \((A_{i_1},B_{i_2})\)，\(m \leftarrow m-1\)；否则询问 \((A_{i_1},B_{i_2})\) 时就变为 \(m=2\) 的情况，能判定排列 \(P\) 不合法。证毕。
有了这个结论，问题就变成了有 \(O(n^3)\) 个有序三元组限制，求有多少个排列 \(P\) 使对所有限制 \((x,y,z)\) 都有 \((P_y-P_x)(P_y-P_z) > 0\)。遗憾的是这个加强后的问题没有什么好办法解决。
维护一张有 \(n\) 个点的无向图。倒序考虑每个询问 \((A_k,B_k)\)，连边 \((A_k,B_k)\)。
注意到，如果加入 \((A_k,B_k)\) 时 \(A_k\) 与 \(B_k\) 并不连通，对于一个与 \(A_k,B_k\) 均不连通的点 \(u\)，由于前面一定询问过 \((u,A_k)\) 及 \((u,B_k)\)，故会产生限制 \((A_k,u,B_k)\)。假设 \(A_k\)（或 \(B_k\)）所在的连通块在排列中的值域相邻，则说明这两块在排列中的值域相邻，显然可以归纳证得。
即建出一棵类似 Kruskal 重构树的二叉树（每个点有 \(0\) 或 \(2\) 个儿子），那么合法的排列 \(P\) 只能这样得到：
- 对于每个非叶节点，可以将它的左右子树交换。
- 中序遍历所有叶节点，得到排列。
记 \(c_u\) 表示是否交换 \(u\) 的左右子树。那么对于剩下的限制 \((x,y,z)\)，记 \(p\) 为 \(x,y,z\) 的 LCA：
- 若 \(p\) 的左右子树内分别含有 \(y\) 及 \(x,z\)，则限制必定被满足。
- 否则不妨设 \(p\) 的左右子树内分别含有 \(x\) 及 \(y,z\)，记 \(q\) 为 \(y,z\) 的 LCA。若 \(y\) 在 \(q\) 的左子树内，则有 \(c_p \neq c_q\)；否则 \(c_p = c_q\)。
把每个 \(c_u=0\) 及 \(c_u=1\) 看作点，对限制连边再遍历一遍即可，如果限制有矛盾则答案为 \(0\)；否则设连通块数量为 \(x\)，则答案为 \(2^x\)。
时间复杂度 \(O(n^3)\)。
Code
D. Distinct Elements on Subsegments (3300)
首先能注意到若有解则 \(| B_{i+1}-B_i | \leq 1\)，同时当其取等时会获得对 \(A_i\) 及 \(A_{i+k}\) 的限制。
记 \(L_i\) 表示 \(A_i\) 是否在 \(A_{i+1},A_{i+2},\cdots,A_{i+k-1}\) 中出现过，\(R_i\) 表示 \(A_i\) 是否在 \(A_{i-1},A_{i-2},\cdots,A_{i-k+1}\) 中出现过，于是有 \(B_{i+1}-B_i=R_{i+k}-L_i\)。
边界：\(B_1=L_1+L_2+\cdots+L_k\)，\(B_n=R_n+R_{n+1}+\cdots+R_{n+k-1}\)。
结论：设 \(\{L_i\}\) 中值为 \(1\) 的位置从小到大为 \(X_1,X_2,\cdots,X_p\)，\(\{R_i\}\) 中值为 \(1\) 的位置从小到大为 \(Y_1,Y_2,\cdots,Y_q\)，若有解则 \(p=q\) 且 \(\forall i \in [1,p],1 \leq Y_i-X_i \leq k-1\)。
证明：对每种颜色 \(x\)，设 \(\{A_i\}\) 中 \(x\) 的位置从小到大为 \(Z_1,Z_2,\cdots,Z_r\)，则对于所有满足 \(Z_{i+1}-Z_i \leq k-1\)，\(L_{Z_i}=R_{Z_{i+1}}=1\)。于是 \(p=q\) 且存在一组 \(\{X_i\}\) 与 \(\{Y_i\}\) 间的匹配使得每一对 \((X_i,Y_j)\) 满足 \(1 \leq Y_j-X_i \leq k-1\)。显然交叉匹配的调换匹配仍然合法，故可调整为顺序匹配，证毕。
事实上，只要 \(\{L_i\}\) 及 \(\{R_i\}\) 满足上述条件，就可以构造一组合法的 \(\{A_i\}\)：
- 设 \(cnt=0\)。从前往后确定每个 \(A_i\)：
- 若 \(R_i=0\)，则令 \(cnt \leftarrow cnt+1,A_i \leftarrow cnt\)。
- 若 \(R_i=1\)，设与 \(Y_t=R_i\) 匹配的 \(X_t\) 为 \(j\)，则令 \(A_i \leftarrow A_j\)。
还剩下最后一个问题：如何由 \(\{B_i\}\) 得到合法的 \(\{L_i\}\) 及 \(\{R_i\}\)？
由于 \(B_{i+1}-B_i=R_{i+k}-L_i\)，故当 \(| B_{i+1}-B_i | = 1\) 时已经确定，问题是 \(B_{i+1}=B_i\) 时如何决策。
结论：若有解，则下面的构造方式一定合法：对于所有 \(B_i=B_{i+1}\)，若 \(B_i < k\)，则令 \(L_i=R_{i+k}=1\)；否则令 \(L_i=R_{i+k}=0\)。对于 \(L_{n+1},\cdots,L_{n+k-1}\) 及 \(R_1,\cdots,R_k\)，\(1\) 的总数已确定，尽量靠中间放。
证明：考虑任意一组合法的 \(\{L_i\}\) 及 \(\{R_i\}\)，若存在 \(B_i=B_{i+1} < k\) 且 \(L_i=R_{i+k}=0\)，将其调整为 \(1\)。由于存在解使得 \(B_i<k\) 且 \(L_i=R_{i+k}=0\)，故该解满足 \(A_{i+1},A_{i+2},\cdots,A_{i+k-1}\) 中有两个相同的数 \(A_x,A_y\)。那么将原匹配 \((x,y)\) 改为匹配 \((i,y)\) 及 \((x,i+k)\)，由之前的结论得 \(\{L_i\},\{R_i\}\) 仍然合法。证毕。
那么按照上面的策略两步构造即可，时间复杂度 \(O(n+k)\)。
Code
E. Grid 3-coloring (3800)
神奇脑洞题，甚至没有 C,D 复杂
先将 \(1,2,3\) 分别替换为 \(0,1,2\)。
结论：对于一个合法的矩阵 \(A\)，存在唯一的矩阵 \(B\) 使得：
- \(B_{i,j} \equiv A_{i,j} \bmod 3\)。
- \(B_{1,1}=0\)。
- \(\forall i>1,|B_{i,j}-B_{i-1,j}|=1\)，\(\forall j>1,|B_{i,j}-B_{i,j-1}|=1\)。
证明：按 \((i,j)\) 字典序升序填数：
- 若 \(i=1\)（或 \(j=1\)），若 \(A_{i,j} \equiv A_{i,j-1}+1 \bmod 3\)，令 \(B_{i,j}=B_{i,j-1}+1\)；否则令 \(B_{i,j}=B_{i,j-1}-1\)。显然填法唯一。
- 否则，若 \(A_{i-1,j}=A_{i,j-1}\)，按上述方式填；否则令 \(B_{i,j}=B_{i-1,j-1}\)。显然填法唯一。
题目给出了边框上的 \(A\) 值，用上述方式可以确定这些位置的 \(B\) 值（如果已经矛盾则无解）。
有解的一个必要条件是对于所有 \(i \in [1,n],|B_{1,i}-B{n,i}| \leq n-1,|B_{i,1}-B{i,n}| \leq n-1\)。
神奇的是，这也是充分条件！直接令 \(B_{i,j}=\max\{B_{1,j}-(i-1),B_{n,j}-(n-i),B_{i,1}-(j-1),B_{i,n}-(n-j)\}\)。考虑 \(B_{i+1,j}-B_{i,j}\)，由于取 \(\max\) 内的四个值均增加了 \(\pm 1\)，故 \(B_{i+1,j}-B_{i,j}=\pm 1\)，故合法。
时间复杂度 \(O(\sum n)\)。
Code
F. LIDS (???)
又是 Anton 的神秘计数题（上一场在 AGC055F），什么时候有闲心了再看