【二次元累積和の練習問題】練習問題 その 1

はじめに

こんにちは！
二次元累積和に絶賛苦しめられているあいすです。まーーじで理解しにくい、のでchat gpt君に教えてもらいながら解いてました。累積和を計算している時に、配列の中身が分かりづらかったので、以下のような感じで教えてもらいました。

例えば、以下のような 3x3 の配列 $a$ を考えます：

1 2 3
4 5 6
7 8 9

累積和配列

この配列 $a$ から累積和配列 $s$ を作ります。累積和配列 $s$ は、元の配列よりも一つ大きい 4x4 の配列にします（最初の行と列はすべて 0 です）。初期状態の $s$ は次のようになります

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

累積和の計算過程

それでは、累積和の計算過程をステップバイステップで見ていきます。

1.$a[0][0]$（値 1）について

s[1][1] = a[0][0] + s[0][1] + s[1][0] - s[0][0]
        = 1 + 0 + 0 - 0
        = 1

結果:
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0

2.$a[0][1]$（値 2）について

s[1][2] = a[0][1] + s[0][2] + s[1][1] - s[0][1]
        = 2 + 0 + 1 - 0
        = 3

結果:
0 0 0 0
0 1 3 0
0 0 0 0
0 0 0 0

3.$a[0][2]$（値 3）について

s[1][3] = a[0][2] + s[0][3] + s[1][2] - s[0][2]
        = 3 + 0 + 3 - 0
        = 6

結果:
0 0 0 0
0 1 3 6
0 0 0 0
0 0 0 0

4.$a[1][0]$（値 4）について

s[2][1] = a[1][0] + s[1][1] + s[2][0] - s[1][0]
        = 4 + 1 + 0 - 0
        = 5

結果:
0 0 0 0
0 1 3 6
0 5 0 0
0 0 0 0

5 $a[1][1]$（値 5）について

s[2][2] = a[1][1] + s[1][2] + s[2][1] - s[1][1]
        = 5 + 3 + 5 - 1
        = 12

結果:
0 0 0 0
0 1 3 6
0 5 12 0
0 0 0 0

6.$a[1][2]$（値 6）について

s[2][3] = a[1][2] + s[1][3] + s[2][2] - s[1][2]
        = 6 + 6 + 12 - 3
        = 21

結果:
0 0 0 0
0 1 3 6
0 5 12 21
0 0 0 0

7.$a[2][0]$（値 7）について

s[3][1] = a[2][0] + s[2][1] + s[3][0] - s[2][0]
        = 7 + 5 + 0 - 0
        = 12

結果:
0 0 0 0
0 1 3 6
0 5 12 21
0 12 0 0

8.$a[2][1]$（値 8）について

s[3][2] = a[2][1] + s[2][2] + s[3][1] - s[2][1]
        = 8 + 12 + 12 - 5
        = 27

結果:
0 0 0 0
0 1 3 6
0 5 12 21
0 12 27 0

9.$a[2][2]$（値 9）について

s[3][3] = a[2][2] + s[2][3] + s[3][2] - s[2][2]
        = 9 + 21 + 27 - 12
        = 45

結果:
0 0 0 0
0 1 3 6
0 5 12 21
0 12 27 45

完成した累積和配列

最終的に累積和配列 $s$ は次のようになります

0 0 0 0
0 1 3 6
0 5 12 21
0 12 27 45

解答

いかがだったでしょうか。めっちゃわかりやすくて感動致しました。まあこれを作り出した人間にさらに驚いております。人類はいったいどこまで進歩するのやら...
上を踏まえたうえでの自分が書いた解答を置いときますね。

<?php
    // 2次元配列を読み込む
    list($n, $w, $h) = explode(" ", trim(fgets(STDIN)));
    for($i = 0; $i < $n; $i++) {
        $a[$i] = explode(" ", trim(fgets(STDIN)));
    }

    // 累積和を計算するための初期化した配列
    // 初期化するときに余分な0をつけてると思いますが、これがポイントです
    $sRow = array_fill(0, $w+1, 0);
    $s = array_fill(0, $h+1, $sRow);

    // 累積和配列の作成
    for($i = 0; $i < $n; $i++) {
        for($j = 0; $j < $n; $j++) {
            $s[$i+1][$j+1] = $a[$i][$j] + $s[$i][$j+1] + $s[$i+1][$j] - $s[$i][$j];
        }
    }

    // 最大値の初期化
    $maxSum = 0;

    // すべてのパターンの長方形領域の合計を求めて、最大値を探す。
    for($i = 0; $i <= $n-$h; $i++) {
        for($j = 0; $j <= $n-$w; $j++) {
            $x1 = $i;
            $y1 = $j;
            $x2 = $i+$h;
            $y2 = $j+$w;
            $sum = $s[$x2][$y2] - $s[$x1][$y2] - $s[$x2][$y1] + $s[$x1][$y1];
            if ($sum > $maxSum) {
                $maxSum = $sum;
            }
        }
    }
    
    echo $maxSum;
    
?>

参考文献

ポイントとして挙げさせていただいたところですが、ここでは解説しません。
以下の投稿で詳しく解説されているので、どこの部分か自分で探してください。

何も考えずに書けるまで何年かかるのか…