【競技プログラミング:リハビリ】2次元累積和

雑記

AtCoderの問題を解けば解くほど、競技プログラミングの鉄則という本の完成度の高さを感じます。
この本を買ったのは、2022年10月だったのだけど、当時読んでたときは「分かりやすい」という感想しかなかったけど、今は「凄い」という感想に。(もう2年半経つとか、時間感覚フリーレン状態ですわ)
スランプに陥ったときはこの本と、過去に完全に理解したことのあるアルゴリズムを読みながら、リハビリをすることにしています。
ということで、スランプ中の今は基本アルゴリズムを、testcase-generatorを使いながら、トレースしつつ眺めてみることにします。

既存投稿一覧ページへのリンク

一覧ページ

二次元累積和

sample_code.py

def cumulative_sum_2d(matrix):
    """
    二次元配列の累積和を計算する関数

    Args:
        matrix (list of list of int): 元の二次元配列

    Returns:
        list of list of int: 累積和を格納した二次元配列
    """
    if not matrix or not matrix[0]:
        return []

    # 元の行列のサイズ
    rows, cols = len(matrix), len(matrix[0])

    # 累積和を格納するための行列を初期化
    cum_sum = [[0] * cols for _ in range(rows)]

    # 累積和を計算
    for i in range(rows):
        for j in range(cols):
            cum_sum[i][j] = matrix[i][j]
            if i > 0:
                cum_sum[i][j] += cum_sum[i - 1][j]  # 上のセルを加算
            if j > 0:
                cum_sum[i][j] += cum_sum[i][j - 1]  # 左のセルを加算
            if i > 0 and j > 0:
                cum_sum[i][j] -= cum_sum[i - 1][j - 1]  # 重複部分を減算

    return cum_sum

if __name__=="__main__":
    # ファイル名を指定
    filename = "./input_data/01.txt"
    
    # 空のリストを準備
    matrix = []
    
    # ファイルを読み込む
    with open(filename, "r") as file:
        for line in file:
            # 行を読み取り、スペースで分割して整数に変換
            row = list(map(int, line.split()))
            matrix.append(row)

    result = cumulative_sum_2d(matrix)

    print("元の行列:")
    for row in matrix:
        print(row)

    print("\n累積和:")
    for row in result:
        print(row)

./input_data/01.txt

77 7 44 55 88 66 48
71 85 19 39 55 4 81
90 72 80 2 0 93 32
20 1 16 67 70 58 30
70 3 21 67 93 79 13
41 24 75 87 75 28 92
88 65 74 93 16 44 31

イメージ

読み込んだデータ

二次元累積和

求めたい領域

累積和を用いた計算

$1842-947-561+402=736$

面積のイメージ