【累積和メニュー】二次元累積和 5 (paizaランク C)-解答例-PHP編

2022年9月12日

【累積和メニュー】> 【二次元累積和】STEP: 5 二次元累積和 5(paizaランク C 相当) [難易度: 1288 ±49]

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

問題文

1 行目に整数 N が与えられます。

2 行目に整数 a, b, c, d が与えられます。

3 行目以降に N 行 N 列の整数の二次元配列 A が与えられます。

A の i 行目 j 列目を A_{i, j} (0 ≦ i ≦ N - 1, 0 ≦ j ≦ N - 1) と表すことにします。

長方形領域の左上の要素を A_{a, b} 、右下の要素を A_{c, d} としたとき、この長方形領域内の整数の和を累積和を用いて求め、一行で出力してください。

入力値（例）
5
1 1 3 3
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

出力値（例）
45

解答例

<?php
    $n = trim(fgets(STDIN));
    list($ax, $by, $cx, $dy) = explode(" ", trim(fgets(STDIN)));
    
    for ($i=0; $i<$n; $i++) {
        $a[$i] = explode(" ", trim(fgets(STDIN)));
    }
    //print_r($a);
        
    $sy = $ax; $sx = $by; $ly = $cx; $lx = $dy;
    $h = $n; $w = $n;
    
    $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);
    
    $ans = $s[$ly+1][$lx+1]-$s[$sy][$lx+1]-$s[$ly+1][$sx]+$s[$sy][$sx];
    echo $ans;
?>

<?php

$n = trim(fgets(STDIN));

list($ax, $by, $cx, $dy) = explode(" ", trim(fgets(STDIN)));

for ($i=0; $i<$n; $i++) {

$a[$i] = explode(" ", trim(fgets(STDIN)));

}

//print_r($a);

$sy = $ax; $sx = $by; $ly = $cx; $lx = $dy;

$h = $n; $w = $n;

$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);

$ans = $s[$ly+1][$lx+1]-$s[$sy][$lx+1]-$s[$ly+1][$sx]+$s[$sy][$sx];

echo $ans;

解答例

カテゴリー