将吃苹果的顺序表示为100个格子的一个排列。如果在吃格子 的苹果之前,已经吃掉了距离它不超过2的其他苹果中的 个,则该苹果得分为 。因此目标函数为 。
可以从随机排列开始模拟退火。使用交换两个位置,或者将一个苹果插入另一位置并移动中间区间等操作。若分数上升则接受;若下降 ,则在温度 下以概率 接受。逐渐降温,多次重新开始,并单独保存历史最高分方案。
每个格子距离2以内的其他格子至多12个。预存邻接列表和当前排列中的位置,只更新先后关系发生变化的格子的 ,即可快速计算分数变化。移动后的位置信息更新至多需要 ,直接重算全部得分也只需 。
模拟退火不能保证达到 AC 门槛。由于网格固定,也可以事先充分搜索,将选定的顺序存入提交程序并直接输出。提供的参考解输出用交换和插入搜索得到的顺序,准确得分为 ,高于 分的门槛,因此获得 AC,超出的分数也会保留。但不声称它是全局最优。参考程序运行时间与输出量成正比,不在提交时进行搜索。
朴素解按行顺序吃苹果。虽然输出是合法排列,但得分较低。
判定可以使用整数准确计算总分。因为 ,将得分乘以 后,每项变为整数 。不对总和设置上限,将实际得分与 的比值作为检查器的得分倍率。子任务满分也是 分,因此即使倍率超过 ,最终得分仍然是苹果得分总和。最终得分达到 分时判定为 AC。每项至多 ,总和至多 ,均在有符号64位整数范围内。
Solution written by GPT6