关于 Arcaea 买曲包的策略问题

学术版

yummy @ 2024-01-11 19:47:03

现有单调递增（不严格）序列 \{a_n\} 满足 a_n\le 20n。 是否总存在一组集合 B_1,B_2,\ldots 和一对正整数 N,K 使得：

Arcaea 语言翻译：

假如 Arcaea 历史平均更新速度不超过 20 首每年，你每年可以获得 100 源点可以买一首歌（第 n 年拥有歌曲集合为 B_n），是否存在策略使得你的 b30 总在所有曲目的前 K 名以内。

举个例子，当 a_n=20n，那么一种构造是：

by yummy @ 2024-01-11 19:50:48

举的例子对应的自然语言：

假如 616 每年更新恰好 20 首歌，你每次都积累 30 年源点然后一次性购买当前定数最高的 30 首歌，那么总可以让你定数前 30 的歌曲永远排在前 600 以内。

by Sol1 @ 2024-01-11 20:13:29

我觉得最优策略就是每年立刻买定数最高的？

这样得到的是 K=581，我觉得没法更低，考虑到最坏情况就是每年 b30 后退 20 位

by yummy @ 2024-01-11 20:16:17

@Solystic 但是如果 616 前 99 年都只更新一首 最后一年给你来 1901 个魔王曲 你第 100 年的 K 就上千了啊

by Sol1 @ 2024-01-11 20:25:18

哦是平均速度...

那我感觉就是类似的，有超过 581 的了就开始买，买到没有为止，应该永远都是够用的？

by yummy @ 2024-01-11 20:36:15

等下我尝试证明下你的结论

|