Project Euler 61

发表于 更新于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

Project Euler 61

题目

Cyclical figurate numbers

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:
Triangle $P_{3,n}=\dfrac{n(n+1)}{2}$ $1, 3, 6, 10, 15, \dots$
Square $P_{4,n}=n^2$ $1, 4, 9, 16, 25, \dots$
Pentagonal $P_{5,n}=\dfrac{n(3n−1)}{2}$ $1, 5, 12, 22, 35, \dots$
Hexagonal $P_{6,n}=n(2n−1)$ $1, 6, 15, 28, 45, \dots$
Heptagonal $P_{7,n}=\dfrac{n(5n−3)}{2}$ $1, 7, 18, 34, 55, \dots$
Octagonal $P_{8,n}=n(3n−2)$ $1, 8, 21, 40, 65, \dots$

The ordered set of three $4$-digit numbers: $8128, 2882, 8281$, has three interesting properties.

  1. The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
  2. Each polygonal type: triangle ($P{3,127}=8128$), square ($P{4,91}=8281$), and pentagonal ($P_{5,44}=2882$), is represented by a different number in the set.
  3. This is the only set of $4$-digit numbers with this property.

Find the sum of the only ordered set of six cyclic $4$-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

解决方案

以题目中的例子$8128, 2882, 8281$说明。

先将$6$个公式中的每一个$4$位数拆分成两块，如$[(81,28),(28,82),(82,81)]$，然后用前一块对应后一块的列表进行存储。

用二进制状态压缩递推（动态规划进行存储）。状态$f(s,i,j),(0<s<2^6,0\le i,j< 100)$表示在使用了一部分的公式下（用$6$比特的$s$表示），序列第一项的前一块为$i$，最后一项的后一块为$j$的情况下，整个序列里面前面一块的和。

序列里所有元素前面一块之和乘$101$就是答案。如$(81+28+82)\times 101$.

由于这个序列是环形的，因此一开始先假设第$0$个公式被使用了。因此，状态值$s$第$0$比特为$0$时，视为不合法状态。

最后答案为$f(2^6-1,i,i)\times 101$。其中$f(2^6-1,i,i)>0,0\leq i < 100$。

具体的转移过程请参考代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
N = 100
M = 6
O = 4
# 一个数4位数拆分成两块，前两位一块，后两位一块。如果第i个式子中的四位数可以表示成100x+y，那么y在列表g[i][x]中。
g = [[[] for j in range(N)] for i in range(6)]
# f[s][i][j]：s是一个状态位，i是一开始的2位，j是当前序列的最后2位。表示当前状态下，所用到的前面一块的和。
f = [[[-1 for j in range(N)] for k in range(N)] for i in range(1 << M)]


def add(p: int, m: int):
    if len(str(m)) == O:
        g[p][m // N].append(m % N)


for i in range(N * N):
    add(0, i * (i + 1) // 2)
    add(1, i * i)
    add(2, i * (3 * i - 1) // 2)
    add(3, i * (2 * i - 1))
    add(4, i * (5 * i - 3) // 2)
    add(5, i * (3 * i - 2))

for x in range(N):
    for y in g[0][x]:
        f[1][x][y] = x

for st in range(1, 1 << M, 2):
    for j in range(N):
        for k in range(N):
            if f[st][j][k] == -1:
                continue
            for p in range(M):
                if st >> p & 1:
                    continue
                for y in g[p][k]:
                    f[st | 1 << p][j][y] = f[st][j][k] + k

ans = max(f[(1 << M) - 1][i][i] for i in range(N)) * 101
print(ans)