【累積和メニュー】> 【二次元累積和】STEP: 1 二次元累積和 1 (paizaランク C 相当) [難易度: 1634 ±37]
※リンク先へ移動するためには[paiza]へのログインが必要です。
5 行 5 列の整数が以下のように与えられます。
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
これを二次元配列 A としたとき、i 行目 j 列目を A_{i, j} (0 ≦ i ≦ 4, 0 ≦ j ≦ 4) と表すことにします。
長方形領域の左上の要素を A_{1, 1}, 右下の要素を A_{3, 3} としたとき、この長方形領域内の整数の和を累積和を用いて求め、一行で出力してください。
左上の要素を A_{1, 1}, 右下の要素を A_{3, 3} としたときの長方形領域とは二次元配列 A のこの領域を指します。
3 4 5
4 5 6
5 6 7
入力値(例)
なし
出力値(例)
長方形領域の左上の要素を A_{1, 1}, 右下の要素を A_{3, 3} としたとき、この長方形領域内の整数の和を累積和を用いて求め、一行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
解答例
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 |
<?php $a = [[1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [3, 4, 5, 6, 7], [4, 5, 6, 7, 8], [5, 6, 7, 8, 9]]; $sy = 1; $sx = 1; $ly = 3; $lx = 3; $h = 5; $w = 5; $sRow = array_fill(0, $w+1, 0); $s = array_fill(0, $h+1, $sRow); for ($i=0; $i<$h; $i++) { for ($j=0; $j<$w; $j++) { $s[$i+1][$j+1] = $a[$i][$j]+$s[$i][$j+1]+$s[$i+1][$j]-$s[$i][$j]; } } //print_r($s); // a[1][1], a[3][3] 領域の和を求める // a[0][0], a[3][3] 領域の和 => s[4][4]: 64 // a[0][0], a[0][4] 領域の和 => s[1][5]: 10 // a[0][0], a[4][0] 領域の和 => s[5][1]: 10 // a[0][0], a[0][0] 領域の和 => s[1][1]: 1 // s[4][4] - s[1][4] - s[4][1] + s[1][1] // 64 - 10 - 10 + 1 = 45 $ans = $s[$ly+1][$lx+1]-$s[$sy][$lx+1]-$s[$ly+1][$sx]+$s[$sy][$sx]; echo $ans; ?> |