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

### はじめに

https://paiza.jp/works/mondai/prefix_sum_problems_advanced/prefix_sum_problems_advanced__2dprefix_practice_step1?language_uid=php

こんにちは！:punch::cow:
二次元累積和に絶賛苦しめられているあいすです。まーーじで理解しにくい、ので`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
<?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;
    
?>
```

### 参考文献

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

https://qiita.com/drken/items/56a6b68edef8fc605821

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