150. 子三角形和(Sub-triangle Sums)

在一个包含正负整数的三角形数组中，我们希望找到一个子三角形，使得它所包含的数字之和尽可能小。

在下面的示例中，可以轻松验证标记的三角形满足此条件，其和为 \(-42\)。

我们希望构建一个有 \(1000\) 行的三角形数组，因此我们生成 \(500500\) 个在 \(\pm 2^{19}\) 范围内的伪随机数 \(s_k\)，使用一种称为线性同余生成器（Linear Congruential Generator）的随机数生成器，方法如下：

\(t := 0\)

对于 \(k = 1\) 到 \(k = 500500\)：

\(\quad t := (615949 \times t + 797807) \bmod 2^{20}\) \(\quad s_k := t - 2^{19}\)

因此：\(s_1 = 273519\)，\(s_2 = -153582\)，\(s_3 = 450905\) 等等。

我们的三角形数组按以下方式使用伪随机数形成：

$$ \begin{matrix} s_1 \\ s_2 & s_3 \\ s_4 & s_5 & s_6 \\ s_7 & s_8 & s_9 & s_{10} \\ \dots \end{matrix} $$

子三角形可以从数组中的任何元素开始，并向下延伸到任意行数（从下一行包含其正下方的两个元素，从下下一行包含其正下方的三个元素，依此类推）。

"子三角形的和"定义为它所包含的所有元素的和。

找到最小的子三角形和。

一、数学背景

本题是二维最大子数组和（Kadane 算法）问题在三角形网格上的推广。给定一个 \(N = 1000\) 行的三角形数组（共 \(N(N+1)/2 = 500{,}500\) 个元素），每个元素 \(A[r][c]\)（\(0 \le c \le r < N\)）的取值范围为 \([-2^{19}, 2^{19}-1]\)，即 \([-524288, 524287]\)。

一个子三角形由其顶点 \((r, c)\) 和高度 \(h\)（\(1 \le h \le N - r\)）唯一定义，包含所有满足以下条件的元素：

$$A[r + i][c + j], \quad 0 \le i < h,\ 0 \le j \le i$$

即第 \(r + i\) 行包含从第 \(c\) 列到第 \(c + i\) 列的 \(i+1\) 个元素。子三角形的和定义为这些元素的算术和。

设 \(S(r, c, h)\) 为以 \((r, c)\) 为顶点、高度为 \(h\) 的子三角形的和，则目标为：

$$\min_{r, c, h} S(r, c, h)$$

本问题中数值范围较大（绝对值和可达 \(2.6 \times 10^{11}\)），需要使用 \(64\) 位整数（Python 的 int 天然支持任意精度，不需要额外处理）。

线段和的计算基于一维前缀和：设 \(\mathrm{pref}[r][i]\) 表示第 \(r\) 行前 \(i\) 个元素的和（\(\mathrm{pref}[r][0] = 0\)），则第 \(r\) 行中列区间 \([c, c+\ell-1]\) 的线段和为：

$$\mathrm{seg\_sum}(r, c, \ell) = \mathrm{pref}[r][c+\ell] - \mathrm{pref}[r][c]$$

二、算法设计

核心思路：逐行扩展

由于 \(N = 1000\) 不算特别大，采用 \(O(N^3)\) 迭代算法配合行前缀和即可在可接受时间内求解。算法的核心循环结构为：

  1. 固定顶点行 \(r\)（外层循环）
  2. 固定顶点列 \(c\)，初始化高度为 \(1\) 的子三角形和
  3. 逐行向下扩展：对于每个高度 \(h = 2, 3, \dots, N-r\)，在已有的 \(h-1\) 高度的子三角形和基础上，加上第 \(r+h-1\) 行中从第 \(c\) 列开始的 \(h\) 个连续元素的线段和

用伪代码表示：

$$ \begin{aligned} &\text{对于每个顶点 } (r, c): \\ &\quad sums[c] \leftarrow A[r][c] \\ &\quad \text{对于 } h = 2 \text{ 到 } N-r: \\ &\quad\quad row \leftarrow r + h - 1 \\ &\quad\quad sums[c] \leftarrow sums[c] + \mathrm{seg\_sum}(row, c, h) \\ &\quad\quad ans \leftarrow \min(ans, sums[c]) \end{aligned} $$

优化措施

  1. 行前缀和：预计算每一行的前缀和数组，使线段和查询降至 \(O(1)\)
  2. 缓存友好的循环顺序：固定顶点行 \(r\) 和当前底行 \(b\) 后，对列 \(c\) 的内层循环连续访问同一行的前缀和数组，CPU 缓存命中率高
  3. 局部变量绑定：将频繁访问的行前缀和数组绑定到局部变量，减少 Python 的全局查找开销

三、复杂度分析

项目 值
时间复杂度 \(O(N^3)\)，\(\approx 1.67 \times 10^8\) 次内层迭代
空间复杂度 \(O(N^2)\)，存储三角数组和行前缀和

时间复杂度推导：

子三角形总数 \(=\) 顶点数 \(\times\) 平均高度：

$$\sum_{r=0}^{N-1} (r+1)(N-r) = \frac{N(N+1)(N+2)}{6} \approx\frac{10^9}{6} \approx 1.67 \times 10^8$$

空间复杂度推导：

实测运行时间：\(\approx 17\) 秒（CPython），远低于 \(60\) 秒的目标。

四、代码实现与说明

"""
Project Euler Problem 150: Sub-triangle Sums

For a triangular array with 1000 rows (500500 elements) generated by
a Linear Congruential Generator, find the minimum sub-triangle sum.
"""


def generate_triangle(n_rows=1000):
    """
    Generate the triangular array using the given LCG.

    t := (615949 * t + 797807) mod 2^20
    s_k := t - 2^19

    Returns:
        list of lists: tri[r][c] is the element at row r, column c.
    """
    total = n_rows * (n_rows + 1) // 2
    t = 0
    MOD = 1 << 20
    HALF = 1 << 19

    tri = []
    row_vals = []
    for k in range(total):
        t = (615949 * t + 797807) % MOD
        row_vals.append(t - HALF)
        # Row r (0-indexed) has r+1 elements.
        if len(row_vals) == len(tri) + 1:
            tri.append(row_vals)
            row_vals = []

    return tri


def build_row_prefix_sums(tri):
    """
    Build prefix sum arrays for each row for O(1) segment sum queries.

    pref[r][i] = sum of tri[r][0] through tri[r][i-1] (inclusive-exclusive).
    So segment tri[r][c:c+h] = pref[r][c+h] - pref[r][c].

    Args:
        tri: The triangular array (list of lists).

    Returns:
        list of lists: pref[r] has length len(tri[r]) + 1.
    """
    pref = []
    for row in tri:
        p = [0] * (len(row) + 1)
        s = 0
        for i, val in enumerate(row):
            s += val
            p[i + 1] = s
        pref.append(p)
    return pref


def solve():
    """Find the minimum sub-triangle sum in the 1000-row triangular array."""
    N = 1000
    tri = generate_triangle(N)
    pref = build_row_prefix_sums(tri)

    ans = float('inf')

    for r in range(N):
        n_cols = r + 1  # number of columns in the top row

        # sums[c] = running sum of triangle with top at (r, c)
        sums = [0] * n_cols

        # Height 1: just the apex elements
        tri_r = tri[r]
        for c in range(n_cols):
            s = tri_r[c]
            sums[c] = s
            if s < ans:
                ans = s

        # Heights 2 through N-r
        max_h = N - r
        for h in range(2, max_h + 1):
            bottom_row = r + h - 1
            pref_b = pref[bottom_row]

            for c in range(n_cols):
                s = sums[c] + pref_b[c + h] - pref_b[c]
                sums[c] = s
                if s < ans:
                    ans = s

    return ans


if __name__ == '__main__':
    result = solve()
    print(result)

代码说明

generate_triangle

build_row_prefix_sums

solve 主函数

 

本站所有文章如非特别声明皆为原创，转载请与作者本人联系并注明出处(原文链接)。 如对文章有任何疑问或需指出错误，可以此页面提出问题，我会尽量及时回复。

←返回主页