题目描述

健忘症患者 Philip 有一个袋子，里面装着 N 颗弹珠，每颗弹珠上都有某种花纹。对于一种花纹，其重要性等于具有该花纹的弹珠个数；对于一颗弹珠，其重要性等于它所属花纹的重要性。

Philip 想要近似地求出所有弹珠重要性之和，记为 H。为此，在第 t 天，他会按某个随机顺序把这些弹珠一颗一颗取出来：

• 观察当前弹珠；
• 对其进行“处理”（即在脑中做一些运算）；
• 然后继续处理下一颗；
• 他不会回头重新看以前的弹珠。

处理完所有弹珠后，他再进行一些最终计算，并给出他对 H 的估计值，记为 Q_t。

之所以只能给出近似值，是因为 Philip 只能记住很少的信息：最多 32 字节。同时，这也是他每天之间互不记忆的原因。

他的目标是设计一个算法，使得：

1. 多天估计值的平均值尽可能接近 H；
2. 其次，每一天的单次估计 Q_t 也尽可能接近 H。

下面更精确地描述 Philip 能看到什么，以及他能记住什么。

他每天会将弹珠按随机顺序取出，并按取出顺序编号为 0 到 N-1。花纹本身也会被随机重新编号为 0 到 N-1，因此两颗弹珠花纹相同，当且仅当它们在当天得到的花纹编号相同。

每天的：

• 弹珠取出顺序；
• 花纹编号方式；

都是独立随机生成的，且与过去所有天数互相独立，所有可能的顺序与编号方式等概率出现。

一开始，Philip 会决定自己要记住多少个整数（int），记这个数量为 S。他更倾向于 S 较小，这样不容易疲劳。

在第 t 天开始时，他记住的 S 个数全为 0。对于每一颗弹珠，他知道：

• N
• 当前弹珠的编号
• 当前弹珠所属花纹的编号
• 处理上一颗弹珠后留下来的 S 个整数

然后他思考一下，决定下一步应该记住哪 S 个整数。所有弹珠处理完毕后，他知道：

• N
• 最终保存下来的 S 个整数

然后再根据这些信息计算出 Q_t。

注意：

• 你可以预先知道一些不会变化的常量，而不必每次重新计算；
• 在处理单颗弹珠或最终计算 Q_t 时，可以使用额外的“工作内存”；
• 但持久记忆只允许使用题目接口给出的状态数组前 S 个元素。

你的任务是帮助 Philip，编写程序 memory.h 来实现这样的算法。你的程序将与评测程序一同编译。

实现要求

你的代码应当写在一个头文件中，并会被评测程序包含。你的代码上方会预先给出如下定义：

using uint = unsigned int;
using ull = unsigned long long;
constexpr uint NUM_TESTS = 10000;
constexpr uint MAX_STATE_SIZE = 8;
using State = std::array<uint, MAX_STATE_SIZE>;

constexpr uint stateSize(uint n);
constexpr void processOne(uint n, uint i, int curr, State& state);
constexpr uint getAnswer(uint n, const State& state);

你需要实现以上三个 constexpr 函数。

constexpr 的含义

函数被声明为 constexpr，意味着它不能产生副作用。更准确地说：

• 不能使用非 constexpr 的全局变量；
• 不能调用带副作用的普通函数；
• 不能进行输入输出；
• 不能依赖运行时状态。

允许做的事情包括：

• 使用局部变量；
• 使用你自己定义的全局 constexpr 常量（只要它们在创建时即可初始化完成）；
• 调用其它 constexpr 函数；
• 使用 if、循环等普通控制结构。

三个函数的要求

stateSize

该函数返回 S，要求满足：

1 <= S <= 8

processOne

该函数会在某一天中，对每一颗弹珠调用一次。

• i 是当前弹珠编号，因此在一天中它会依次取值为 0,1,2,...,N-1
• curr 是当前弹珠的花纹编号
• state 是当前保存的状态

每天开始时，state 全为 0。此外，为了保证你真的只使用前 S 个 int 的持久记忆，评测程序会在每次处理完一颗弹珠后，把 state 中除前 S 个元素以外的其它元素全部清零。

getAnswer

该函数在一天结束后被调用，需要根据最终状态返回 Q_t。

总共有：

T = 10^4

天。

关于编译时检查

由于 C++ 标准并不强制 constexpr 函数在所有场景下都必须真正于编译期求值，因此评测程序中会包含一个内置测试：你的程序会在编译期间被运行一次；如果在该测试上不能作为 constexpr 正常执行，则不会通过编译。

注意，理论上你可以故意写出一种程序：

• 在某些情况下可作为 constexpr 工作；
• 但在另一些情况下又偷偷依赖全局变量等非法手段。

如果发现此类解法，成绩会被取消；重复违规可能会被取消比赛资格。

另外，由于评测程序等价于在编译期运行你的程序完整测试一次，因此在极端情况下，编译本身也可能出现 ML 或 TL。不过这通常只有在你的程序本来就会非常慢、非常耗内存、或者存在很深递归时才会发生。

限制

• N = 10^3 恒成立
• 0 <= i, curr < N

评分方式

每个测试点得分在 0 到 1 之间。

某个子任务的得分为：

• 该子任务最大分值
• 乘以该子任务内所有测试点中的最小得分

下面说明单个测试点如何计分。

首先定义：

E = rac{1}{T}\sum_{0 \le t < T}(Q_t - H) $$R = \sqrt{rac{1}{T}\sum_{0 \le t < T}(Q_t - H)^2}$$

也就是说：

• E 是你的程序的平均误差；
• R 是你的程序的均方根误差。

目标是使 |E| 和 R 都尽可能小。更具体地，定义：

$$U = \left|\ln\left(rac{1 + H + E}{1 + H} ight) ight| imes \sqrt{S}$$$$V = \ln\left(rac{1 + R imes\sqrt{S}}{\ln(H)} ight) \Big/ H$$

直观上：

• U 用对数尺度衡量线性误差。例如 Q_t = H/2 与 Q_t = 2H 会被认为同样糟糕；
• V 从另一种角度衡量平方误差。

二者都会额外乘上 \sqrt{S}，即若你使用 4 倍的状态空间，却只把误差缩小到原来的一半，那么最终得分不会改善。

再定义函数：

$$B(x) = \min(\max(x, 0), 1)$$

最终得分为：

$$B(3^{0.005-U}) imes \left(0.35 + 0.65 imes B\left(1 - rac{V-0.85}{0.3} ight) ight)$$

换言之：

• 若 U <= 0.005 且 V <= 0.85，则该测试点得满分；
• 若 U <= 0.005 且 V >= 1.15，则得分为 0.35；
• 若 U > 0.005，得分会随 U - 0.005 指数下降。

本地测试

题目提供以下文件：

• Lgrader.cpp
• Lgrader2.cpp
• memory_example.h

Lgrader.cpp

它模拟正式评测器，可用于本地测试。编译方式为：只编译这个文件，并保证你的解答 memory.h 与它位于同一目录。

输入格式为：

• 先输入花纹种类数与随机种子；
• 然后输入每种花纹对应的弹珠数量。

程序会输出：

• E
• R
• U
• V
• 最终得分

Lgrader2.cpp

与 Lgrader.cpp 基本等价，但不要求你的函数为 constexpr。因此在开发初期，你可以用它来调试、输出信息等。

memory_example.h

这是一个合法的示例程序，用来展示在 constexpr 限制下允许进行哪些操作。

子任务

编号	分值	附加限制
1	20	每种出现过的花纹数量大致相等。也就是说，存在一个整数 X，使得每种花纹的出现次数只可能是 0、X 或 X+1。
2	80	无额外限制。

说明： 子任务 2 包含子任务 1 的所有测试。