Santa 第5名解决方案 (2428) & 洞察

首先祝贺所有在这次比赛中取得好成绩的人。我很高兴能获得单人金牌。我大部分时间是在纸上解决这个问题，然后编写代码。以下是我的详细解决方案：

命名约定：

序列分为3种类型：

1. 强制性 (M) - 以 '12' 开头的序列 - (120个)
2. 强制性亲属 (R) - 包含 '12' 但不以它开头的序列 - (120*5个)
3. 非强制性非亲属 (N) - 所有其他序列 - (4320个)

解决方案：

1. 证明下界 = 2400（不使用通配符，数学方法）

由于问题中引入了额外的约束，这变得很容易。在包含超过8个序列的循环排列中，我们能拥有的最佳长度/序列比是 7/6（6个长度为1的边后跟一个长度为2的边 - 2个循环）。解决方案中将有 120*3 个 M。这强制要求额外的约束 - 120 * 5 * 3 个 R。因此，我们的排列必须包含这 120 * 5 * 2 个额外的重复项。

让我们计算下界

• N - 4320 * 7/6 = 5040
• R - 3 * 120 * 5 = 1800
• M - 120 * 3 = 360
• 总长度 = 7200
• 如果我们可以将此循环在7边处（如果有）分割成3个等长的排列，我们会得到 2400。但我们为了最佳情况放宽了一些约束。也许加上这些约束在数学上能让我们达到 2440。

2. 达到 2440

• 这与其他参与者的做法相似。我脑海中大约有 N, R, M 的计数，起初我不想在2个循环中打破 N-N 连接。这可能是我运气好的地方，如果我从2个循环中移除所有 R 并只保留一个 M，我会得到每个循环长度为 47 的排列（我们称之为 B，基础排列）。简单连接所有这 120 个循环。我有长度为 120 * 47 = 5640 的排列，其中包含所有 N 序列。

长度为 47 的样本基础排列 (B): 12345672134567231456723415672345167234561723456

• 现在，对于 M & R -> 我们可以将在末端位置交换字符的 M 序列对组合起来，如 '12345671234576'。我们可以轻松建立这些连接，通过在每个 120 个基础排列的开头附加相应的序列，这使得每个基础排列的长度变为 47+7 = 54。总长度 = 120 * 54 = 6480。

长度为 54 的样本基础排列 (B): 123457612345672134567231456723415672345167234561723456

• 每个2循环中只剩下要添加的序列 - #12#### (7123456)。现在，让我们添加一个长度为 7 的 M，唯一的约束是它以 '7' 结尾。基础排列长度 = 54 + 7 = 61。总长度 120*61 = 7320。

长度为 61 的样本基础排列 (B): 1236547123457612345672134567231456723415672345167234561723456

• 在每个子排列中使用 40 个长度为 61 的排列以达到 2440。我可以直观地证明这一点，但在 @cpmpml 和其他人的确认后，我确信这是下界。

3. 达到 2428

• 一旦你确切知道你的解决方案是如何创建的，达到 2428 就很容易了。为了达到 2428，我们可以修改我们的排列，并在长度为 47 的基础排列的末尾而不是开头添加相应的序列。这种通配符排列（长度为 48）的对（在最后位置交换）将覆盖长度为 54 的基础排列中包含的所有序列。我们错过了 R，但我们有额外的 M 来弥补它。记住，我们需要堆叠 2 个 M 来保存所有 R (12345671234576)。我们可以为这 6 个特殊的通配符情况堆叠 3M (124356712345671234765)

长度为 48 的样本通配符排列 (B): 12345672134567231456723415672345167234561*234576

• 我们的解决方案大小 -> 从 54 减少到 48（节省 6 个长度）。6 个通配符 - 3 对 - 2428 解决方案。

4. 为什么我认为 2428 是最优的，并且在最佳解决方案中每个通配符只能节省 6

假设我们只能通过断开和建立连接来使用通配符

• 我们无法节省 R。R 平均重复 3 次。如果我们使用通配符在一个地方节省 R，它仍然会出现在其他地方。我的意思是技术上我们可以节省 R。但是，当我们节省 R 时，我们实际上移除了一条冗余的边。
• 触及长度为 47 的基础排列（除了开头或结尾） - 基础排列是饱和的。只有长度为 1 或 2 的边。（6 个 1 后跟一个 2）
• 情况