LOJ #3831. 「IOI2022」囚徒挑战 题解

Description

一个监狱里关着 $500$ 名囚徒。 有一天，监狱长给了他们一个重获自由的机会。 他把装钱的两个袋子 A 和 B 放在一个房间里。 每个袋子装有若干枚硬币，数量的范围在 $1$ 到 $N$ 之间（包含 $1$ 和 $N$）。 两个袋子里硬币的数量不同。 监狱长给囚徒们提出了挑战，目标是指出硬币数量较少的那个袋子。

房间里除了袋子还有一块白板。 任意时刻白板上写着一个数，一开始写的是 0。

监狱长让囚徒一个接一个地进入房间。 每个进入房间的囚徒不知道他之前进入过房间的囚徒有多少人，也不知道是哪些人。 每次一个囚徒进入房间时，他看一眼白板上目前写的这个数。 看完之后，他必须在袋子 A 和 B 之间做出选择。 接着，他检查自己选的那个袋子，知道了里面有多少枚硬币。 然后，这名囚徒必须选择做以下两种行动之一：

• 将白板上的数改写成一个非负整数，并离开房间。 注意他可以改变成新的数，也可以保留当前的数。 然后挑战继续进行（除非所有 $500$ 名囚徒都已经进过房间）。
• 指出硬币数量较少的那个袋子。这会立即结束挑战。

对于已经进过房间的囚徒，监狱长不会让他再次进入房间。

如果某个囚徒正确地指出硬币较少的袋子，则囚徒们获得挑战的胜利。 如果指出的袋子不正确，或者所有 $500$ 人进过房间之后还没有人尝试指出硬币较少的袋子，则囚徒们失败。

挑战开始之前，囚徒们集合在监狱大厅商量应对挑战的共同策略，分以下三个步骤：

• 他们挑选一个非负整数 $x$，作为他们可能会写在白板上的最大的数。
• 他们决定对任意一个数 $i (0 \le i \le x)$，如果某个囚徒进入房间后看到白板上写着数 $i$，那么他应该去检查哪个袋子。
• 他们决定当某个囚徒得知选中的袋子里的硬币数量后要采取的行动。具体来说，对任意写在白板上的数 $i (0 \le i \le x)$ 和检查选中的袋子里的硬币数量 $j (1 \le j \le N)$，他们要决定做出以下两种行动之一：
  • 白板上应该要写一个 $0$ 到 $x$ 之间（包含 $0$ 和 $x$）的什么数；
  • 指出哪个袋子是硬币较少的。

如果赢得挑战，监狱长会在囚徒们继续服刑 $x$ 天后释放他们。

$N\leq 5000,x=20$。

Solution

首先这题有个很简单的想法是按照 $2$ 进制从高位到低位进行比较，并且把上一位的值压在状态里。即从高位到低位的第 $i$ 位，如果当前数是 $0$，则为 $2i+1$，否则为 $2i+2$。然后对于这两种状态去询问与它们之前询问的数不同的那个，即可得到另一个数的值，如果能在第 $i$ 位比较出来，则直接结束。否则递归到第 $i+1$ 位，同时每次询问的数交替即可。

这么做是 $2\left\lceil\log_2N\right\rceil=26$ 次，不太能过。改成 $3$ 进制可以变成 $24$ 次。

考虑优化。由于最后一定能比出大小，所以递归到最低位时，如果当前位为 $0$ 或者 $2$，则可以直接返回。于是就变成 $22$ 次了。

上面的做法已经不好优化了，考虑将 $3$ 进制改成类似线段树的结构，即我们可以确定当前数在 $[l,r]$ 的范围内，然后询问另一个数，如果能比出大小就结束，否则将 $[l,r]$ 平均分成 $3$ 份进行处理，显然这是和原先的做法等价的。

这个做法和上面的小优化容易结合起来，即如果询问出来的数为 $l$ 或者 $r$ 就能结束，也就是区间长度 $k$ 变为 $\left\lceil\frac{k-2}{3}\right\rceil$，经过计算次数变为 $21$ 次。

最后的优化就是注意到区间长度不超过 $6$ 时进行三分是很浪费的，因为划分后长度为 $1$ 还是 $2$ 是一样的，所以这个时候二分是一样的，总次数就变为 $20$ 次了。

Code

#include "prison.h"
#include <bits/stdc++.h>

const int kV[] = {3, 3, 3, 3, 3, 3, 2}, kS[] = {0, 3, 6, 9, 12, 15, 18, 20};

int N;
std::vector<std::vector<int>> res;

void solve(int d, int x, int l, int r, int L, int R) {
  if (l > r) return;
  int op = (d & 1);
  res[x][0] = op;
  int v = (d <= 6 ? kV[d] : 1), len = r - l - 1, k[v] = {0};
  for (int i = 0; i < v; ++i) k[i] = (len + v - 1 - i) / v;
  for (int i = L; i <= R; ++i) {
    if (i <= l) {
      res[x][i] = -op - 1;
    } else if (i >= r) {
      res[x][i] = op - 2;
    } else {
      res[x][i] = kS[d];
      for (int j = 0, s = l + 1; j < v; s += k[j++]) res[x][i] += (i >= s);
    }
  }
  for (int i = 0, s = l + 1; i < v; s += k[i++]) solve(d + 1, kS[d] + 1 + i, s, s + k[i] - 1, l, r);
}

std::vector<std::vector<int>> devise_strategy(int N) {
  res.resize(21, std::vector<int>(N + 1, 0));
  ::N = N, solve(0, 0, 1, N, 1, N);
  return res;
}