【累積和メニュー】> 【2 次元上のいもす法】STEP: 2 2 次元上のいもす法 2 (paizaランク C 相当) [難易度: 1566 ±45]
※リンク先へ移動するためには[paiza]へのログインが必要です。
問題文
1 行目に a_i, b_i (1 ≦ i ≦ 5) が 5 行で与えられます。
5 行 5 列のマスがあり、最初、マスには全て 0 が書かれています。
5 つの長方形領域の左上の座標 (a_i, 3) と右下の座標 (b_i, 3) が与えられます。それぞれの範囲に対して、その範囲に含まれるマスに 1 を加算していきます。
5 行 5 列のマスに書かれた値のうち、最大の値をいもす法を用いて求めてください。
入力値（例）
1 3
2 4
3 5
1 3
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 43 44 45 46 47 48 |
<?php for ($i=0; $i<5; $i++) { list($a, $b) = explode(" ", trim(fgets(STDIN))); $x1[] = $a; $x2[] = $b; } $sRow = array_fill(0, 6, 0); $s = array_fill(0, 6, $sRow); //$x1 = [1,2,3,1,3]; $y1 = [3,3,3,3,3]; //$x2 = [3,4,5,3,5]; $y2 = [3,3,3,3,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; ?> |
