【累積和メニュー】> 【2 次元上のいもす法】STEP: 1 2 次元上のいもす法 1 (paizaランク C 相当) [難易度: 1545 ±44]
※リンク先へ移動するためには[paiza]へのログインが必要です。
5 行 5 列のマスがあり、最初、マスには全て 0 が書かれています。
x 座標を列、y 座標を行とします。以下に
(左上の x 座標, 左上の y 座標) (右下の x 座標, 右下の y 座標)
(1 ≦ x ≦ 5, 1 ≦ y ≦ 5)
という形で、マスに沿った長方形の 5 つの範囲が与えられます。それぞれの範囲に対して、その範囲に含まれるマスに 1 を加算していきます。
5 行 5 列のマスに書かれた値のうち、最大の値をいもす法を用いて求めてください。
(1, 1) (3, 3)
(2, 2) (4, 4)
(3, 3) (5, 5)
(1, 3) (3, 5)
(3, 1) (5, 3)
入力値(例)
なし
出力値(例)
5 行 5 列のマスに書かれた値のうち、最大の値をいもす法を用いて求めてください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
解答例
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 32 33 34 35 36 37 38 39 40 41 42 |
<?php $sRow = array_fill(0, 6, 0); $s = array_fill(0, 6, $sRow); $x1 = [1,2,3,1,3]; $y1 = [1,2,3,3,1]; $x2 = [3,4,5,3,5]; $y2 = [3,4,5,5,3]; for ($i=0; $i<5; $i++) { $s[$y1[$i]-1][$x1[$i]-1]++; $s[$y2[$i]][$x2[$i]]++; $s[$y1[$i]-1][$x2[$i]]--; $s[$y2[$i]][$x1[$i]-1]--; } // 横方向への累積和 for ($i=0; $i<6; $i++) { for ($j=1; $j<6; $j++) { $s[$i][$j] += $s[$i][$j-1]; } } // 縦方向の累積和 for ($i=1; $i<6; $i++) { for ($j=0; $j<6; $j++) { $s[$i][$j] += $s[$i-1][$j]; } } //print_r($s); // 最大値を調べる $tile_max = 0; for ($i=0; $i<6; $i++) { for ($j=0; $j<6; $j++) { if ($tile_max < $s[$i][$j]) { $tile_max = $s[$i][$j]; } } } echo $tile_max; ?> |