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