【累積和メニュー】2 次元上のいもす法 3 (paizaランク C)-解答例-PHP編

2022年9月15日

【累積和メニュー】> 【2 次元上のいもす法】STEP: 3 2 次元上のいもす法 3 (paizaランク C 相当) [難易度: 1414 ±51]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

1 行目に a_i, b_i, c_i, d_i (1 ≦ i ≦ 5) が 5 行で与えられます。

5 行 5 列のマスがあり、最初、マスには全て 0 が書かれています。

5 つの長方形領域の左上の座標 (a_i, b_i) と右下の座標 (c_i, d_i) が与えられます。それぞれの範囲に対して、その範囲に含まれるマスに 1 を加算していきます。

5 行 5 列のマスに書かれた値のうち、最大の値をいもす法を用いて求めてください。

入力値（例）
1 1 3 3
2 2 4 4
3 3 5 5
1 3 3 5
3 1 5 3

出力値（例）
5

解答例

<?php
    $sRow = array_fill(0, 6, 0);
    $s = array_fill(0, 6, $sRow);

    for ($i=0; $i<5; $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<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;
?>

<?php

$sRow = array_fill(0, 6, 0);

$s = array_fill(0, 6, $sRow);

for ($i=0; $i<5; $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<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;

解答例

カテゴリー