Avoid Boring Matches Editorial

# [E - 避免无聊的比赛](https://atcoder.jp/contests/arc169/tasks/arc169_e) 解读

*作者 [maroonrk_admin](https://atcoder.jp/users/maroonrk_admin)*

---

首先，我们考虑在固定 $S$ 的情况下能否达成目标。

我们关注参与者 $1$。

如果参与者 $1$ 的帽子是红色，那么必须与一个戴蓝色帽子的参与者配对。考虑到比赛的结果参与者 $1$ 必然会胜出，我们选择编号最大的戴蓝色帽子的参与者，这样就不会吃亏。因此在这种情况下可以确定配对。

如果参与者 $1$ 的帽子是蓝色，那么与比赛对手的帽子颜色没有限制。如果还有戴红色帽子的参与者，那么可以与其中编号最小的人配对，这样不会吃亏。如果所有人都是戴蓝色帽子的话，可以与编号最大的参与者配对，这样同样不会吃亏。因此在这种情况下也可以确定配对。

由此，我们确定了参与者 $1$ 的配对。移除该配对后，按照同样的讨论，编号最小的参与者的配对也会确定。通过重复这个操作，可以最终决定所有的分组，从而进行比赛，这样就能够判断目标是否能够达成。

至此我们已经了解了在固定 $S$ 的情况下的判定方法，但要想解决原始问题，还需要进一步理清思路。

直观地看，

- $S$ 中 `B` 的数量越多，达成目标的可能性越高；
- $S$ 中 `B` 的位置越靠左，达成目标的可能性越高。

因此，我们考虑的是能够达成目标的 $S$，它包含尽可能少的 `B`，并且尽量靠右。我们将其称为极小的 $S$。至于“尽可能靠右”的定义虽然比较模糊，但无论如何决定，都可以得到相同的结论。同时，极小的 $S$ 不一定是唯一的，但通过后面的讨论可以证明它是唯一的。

通过适当的手动操作，可以发现对于小的 $N$，以下 $S$ 是极小的。

- $N=1$: $S=$ `RB`
- $N=2$: $S=$ `RBRB`
- $N=3$: $S=$ `RBRRBRBB`

通过考虑最初说明的贪心法的“反向”，我们可以得到更大 $N$ 的极小 $S$。

我们用 $T(N)$ 来表示某个 $N$ 的极小 $S$。利用 $T(N)$ 来表征目标能够达成的 $S$，那么这将满足以下条件。

- $S$ 中的 `R` 和 `B` 分别被替换为 $-1$ 和 $+1$，并且取累积和后形成的数列称为 $A$。类似地，$T(N)$ 中的 `R` 和 `B` 也分别被替换为 $-1$ 和 $+1$，形成的数列称为 $B$。如果对于所有的 $i$，$A_i \geq B_i$，那么目标可达；否则目标不可达。

证明可以通过归纳法进行。如果存在某个 $i$ 使得 $A_i < B_i$，首先取这样的 $i$ 中最小的。然后观察在位置 $i$ 之前进行贪心分组时的状态。可以发现，经过 $1$ 回合后，$S$ 不满足条件。

反之，如果所有的 $i$ 都有 $A_i \geq B_i$，那么 $S$ 满足条件，这一点很容易验证。

到此为止，问题就变得简单了。最终问题是：

- 给定一个 $+1,-1$ 的序列，通过反复进行相邻的交换，使得累积和达到某个特定值以上。

答案是累积和与目标的差值除以 $2$。

上述操作都可以在 $O(2^N)$ 的时间复杂度内完成，因此原始问题也可以在相同的计算量下解决。

[解答例](https://atcoder.jp/contests/arc169/submissions/48277475)