第三名方案

首先，我要感谢主办方提供了又一年有趣的问题，也感谢所有其他参赛者让这场比赛变得非常有趣。我要感谢我的队友 @nagiss、@kibuna 和 @hiroakikitahara 的出色合作。

在这篇文章中，与其直接解释 2428 分的解决方案，我想解释我们是如何一步步思考的。这可能会有点长，但我希望它能有所帮助。

第一步

由于处理 🌟（星号）很复杂，而且我们最多只能使用两个 🌟，我们首先致力于不使用 🌟 的解决方案。如果我们固定每个排列出现在三个字符串中的哪一个，我们可以将问题视为非对称旅行商问题（ATSP）。由于共有 7! 个排列和 2 * 5! 个额外的强制排列，如果排列可以平均分配到三个字符串中，每个字符串的顶点数约为 (7! + 5! * 2) / 3 = 1760。这个 1760 个顶点的 ATSP 可以使用 LKH 和 Concorde* 在现实时间内最优解决。因此，我们只需要考虑如何将排列分配给这三个字符串。

*这意味着对于这个问题是可行的，并不是说在一般情况下都可行。例如，n = 6 的超排列是一个有 720 个顶点的 ATSP，但一般认为 Concorde 很难直接找到最优解 (Houston 2014)

基于 2-cycle 的分配（得分：2480）

首先，我们考虑分配 5040 个排列，使它们包含相同数量的强制排列。考虑到其他排列应该是什么样子，似乎可以以成本 1 移动的排列（例如 7123456 -> 1234567）应该尽可能在同一个字符串中。此外，我们希望一个由可以以成本 1 移动的排列组成的组（例如 2345671 -> 3456712 -> … -> 1234567），以及一个可以以成本 2 从该组移动的组（例如 3456721 -> 4567213 -> … -> 1345672。从 1234567 到 3456721 的成本是 2），在同一个字符串中。重复这种成本 2 的组间移动 n (= 7) 次会将其带回原始组并形成一个循环。在超排列的上下文中，这个循环被称为 2-cycle（有关更精确的定义，请参阅链接）。我们尝试使用这个 2-cycle 来进行分配。

共有 120 个 2-cycle，因此其中 40 个被分配给三个字符串中的每一个。每个 2-cycle 恰好包含一个强制排列，因此此时每个字符串将包含 40 个强制排列。通过添加尚未添加的 80 个强制排列，我们可以满足问题中的约束。

伪 Python 代码如下所示。在使用 LKH 或 Concorde 通过随机 2-cycle 分配将问题作为 ATSP 求解几次迭代后，达到了 2480 的分数。我们尝试了各种 2-cycle 分配方法，但在没有下一节描述的 2-cycle 拆分的情况下，无法找到低于 2480 的解决方案。

twocycle_nodes = []
for v in ["12" + "".join(s) for s in itertools.permutations("34567")]:
    nodes = []
    for y in range(6):
        nodes.append(v)
        v = v[2:] + v[1] + v[0]
        for x in range(6):
            nodes.append(v)
            v = v[1:] + v[0]
    assert v == twocycle
    twocycle_nodes.append(nodes)

assignment = np.arange(120) % 3
np.random.shuffle(assignment)

groups = [[], [], []]
for idx_groups, nodes in zip(assignment, twocycle_nodes):
    #