AT_arc138_c [ARC138C] Rotate and Play Game 题解

AT_arc138_c [ARC138C] Rotate and Play Game 题解

ATcoder 原题链接
洛谷链接
蒟蒻太菜了，打模仿赛被此题爆杀，发现此题从思考方式和题目转化上都有较大启发，故写一篇题解纪念。^^
I. 题意

有 \(n\) 张卡牌编号为 \(1\sim n\)，第 \(i\) 张卡片上的数为 \(a_i\)。先手 Snuke 可以拿走恣意一张牌，后手 Min 只能拿走最左边的牌。Snuke 的得分为他拿走的牌的分数总和，目标要使 Snuke 的得分最大。
有一种操纵，选择一个数 \(k(0\le k\le n - 1)\)，将卡牌数列左移 \(k\) 位，即讲卡牌顺序变为 \(a_{k + 1}, a_{k + 2}, \dots, a_n, a_1, a_2, \dots, a_k\)。
求问符合条件的恣意 \(k\) 和 Snuke 的最大得分。
II.思路

首先，我们有如下几个显而易见的条件：

• 游戏会进行 \(\frac{n}{2}\) 轮，Snuke 只能拿走 \(\frac{n}{2}\) 张卡牌；
  
• Snuke 如何操纵，\(k\) 如何变幻，Snuke 的分数理论最大为 \(n\) 张卡牌中分数前 \(\frac{n}{2}\) 大的卡牌。
  
• Min 只会取最左边的牌，不会干扰我们取牌。也就是说，\(k\) 和 Snuke 拿牌顺序一定，那么 Min 会取哪些拍我们也知道。
  

那么我们尝试想：我猜出题人肯定想让我拿满这个上界。如果我能构造出一种环境让 Snuke 把全部大数全拿走，那就直接赢了，不用考虑复杂的博弈。
于是，Snuke 的目标变为拿走分数前 \(\frac{n}{2}\) 的卡牌，所以分数确定。故而这 \(n\) 个数在我们眼中，只有分数是否为前 \(\frac{n}{2}\) 大是被我们所关注的。所以，我们将分数前 \(\frac{n}{2}\) 的卡牌标记为 \(1\)，否则标记为 \(0\)。
其次，要想分数为理论最大值，Snuke 就要拿走全部的 \(1\)，而 Min 只能拿 \(0\)。
直接考虑方案感觉较难，考虑正难则反，看怎么拿牌会破坏让 Min 只拿 \(0\) 的约定。观察第 \(i\) 轮 Min 拿牌后：

• 此时 Snuke 和 Min 各拿走 \(i\) 张牌，总共 \(2\times i\) 张牌被拿走。
  
• 若这 \(2\times i\) 张牌中，\(1\) 的数量大于 \(i\) 张，则纵然 Snuke 拿走 \(i\) 张 \(1\)，Min 也会拿走至少 \(1\) 张 \(1\)，不满足条件。
  

综上，若我们要 Min 拿不到任何 \(1\)，前 \(2\times i\) 个位置里，要保持 \(1\) 的数量不大于 \(0\) 的数量。
这不是 Catalan 数板子题吗？不过这不是计数题，我们考虑参考 Catalan 数的解法：
考虑将问题转化成：你初始时站在已平面直角坐标系中，位于点 \((0, 0)\)，牌堆为操纵序列， \(1\) 是向上走 \(1\) 单位，\(0\) 是向下走 \(1\) 单位。
以样例 5 9 7 4 2 8 2 3 为例，则序列转换为 1 1 1 0 0 1 0 0，如下图：

显然这个样例最有环境为 \(k = 3\) 时得分为最大值 \(29\)。我们猜测这个 \(k\) 可能与折现最高点有关。
更严谨地，设原标记序列为 \(b_1,b_2,\dots,b_n\)，其中大牌记作 \(+1\)，小牌记作 \(-1\)（这里把前面的 \(0\) 换成 \(-1\) 只是为了求和方便，不影响本质）。定义前缀和

\[S_0=0,\quad S_i=\sum_{j=1}^{i} b_j \quad (1\le i\le n)\]
由于大牌和小牌各占一半，所以 \(S_n=0\)。
如今考虑循环左移 \(k\) 位后的序列，它的第 \(i\) 个前缀和为

\[S'_i = \begin{cases}S_{k+i}-S_k, & k+i \le n,\\S_{k+i-n}+S_n-S_k = S_{k+i-n}-S_k, & k+i>n.\end{cases}\]
由于 \(S_n=0\)，上面两式可以同一写成 \(S'_i = S_{(k+i)\bmod n} - S_k\)，其中 \(S_n=S_0=0\)。
我们要让 Min 始终拿不到大牌，等价于要求恣意前缀中大牌数不超过小牌数，即 \(\forall i=1,2,\dots,n\)，有 \(S'_i \le 0\)。
而 \(S_{(k+i)\bmod n}\) 遍历了 \(S_0,S_1,\dots,S_{n-1}\)（当 \(i\in [1, n]\) 时，\((k+i)\bmod n\) 正好遍历全部剩余下标）。因此，要使全部 \(S'_i\le 0\)，只需 \(\forall j=0,1,\dots,n-1\) 有 \(S_k \ge S_j\)。
即 \(S_k\) 是这些前缀和中的最大值。
所以，最优的 \(k\) 就是前缀和序列 \(S_0,S_1,\dots,S_{n-1}\) 中最大值第一次出现的位置（下标从 \(0\) 开始）。若最大值在位置 \(p\)，则令 \(k=p\)（若 \(p=0\) 则输出 \(0\)，否则输出 \(p\)，由于循环左移 \(p\) 位恰恰对应）。这就是为什么我们在代码中要找前缀和的最大值，最后输出时还要把下标减 \(1\)（由于代码里下标从 \(1\) 开始，而最大值位置 \(mxp\) 是 \(1\)-based，实际 \(k=mxp-1\)）。
III.代码

[code]#include#define endl '\n'#define pi pair#define int long longusing namespace std;const int N = 2e5 + 10;int n, b[N];struct node{        int x, id;        bool operator> n;    for (int i = 1; i > a.x;            // a.y = a.x;            a.id = i;    }    sort(a + 1, a + 1 + n);    int ans = 0;    for (int i = n / 2 + 1; i