【クエリメニュー】二次元区間和 (paizaランク B)-解答例-PHP編

2022年9月1日

【クエリメニュー】> 【平方分割】STEP: 4 二次元区間和 (paizaランク B 相当) [難易度: 1725 ±29]

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

問題文

H 行 W 列の行列 A の 2 つの行・列番号の組 {a , b} , {c , d} における区間和 S({a,b} , {c,d}) (a ≦ c , b ≦ d) を以下の数式・図の通り定義します。以後 A の y 行 x 列の要素を A[y][x] と表すことにします。

S({a,b} , {c,d}) = A[a][b] + A[a][b+1] + ... + A[a][d] + A[a+1][1] + ... + A[a+1][d] + ... + A[c][1] + ... + A[c][d]

例として、入力例 1 の A における S({2,2},{3,3}) は以下の通りになり、値は 28 となります。

H 行 W 列の行列 A と、区間和を求めたいペアについての情報が与えられるので、各ペアについて累積和を求めてください。

入力値（例）
3 3 2
1 2 3
4 5 6
7 8 9
1 1 3 3
1 2 2 3

出力値（例）
45
16

解答例

<?php
    list($h, $w, $n) = explode(" ", trim(fgets(STDIN)));
    
    $sum = [[]];
    
    for ($i = 0; $i < $h; $i++) {
        $a[$i] = explode(" ", trim(fgets(STDIN)));
        
        for ($j = 0; $j < $w; $j++) {
            $sum[$i][$j] = $a[$i][$j];
            
            if (0 < $i) $sum[$i][$j] += $sum[$i-1][$j];
            if (0 < $j) $sum[$i][$j] += $sum[$i][$j-1];
            if (0 < $i && 0 < $j) $sum[$i][$j] -= $sum[$i-1][$j-1];
        }
    }
    //print_r($sum);
    
    for ($i = 0; $i < $n; $i++) {
        list($a, $b, $c, $d) = explode(" ", trim(fgets(STDIN)));
        
        $a--; $b--; $c--; $d--;
        
        if ($a>0 && $b>0) {
            $ans = $sum[$c][$d]+$sum[$a-1][$b-1]-$sum[$a-1][$d]-$sum[$c][$b-1];
        } else if ($a==0 && $b>0) {
            $ans = $sum[$c][$d]-$sum[$c][$b-1];
        } else if ($a>0 && $b==0) {
            $ans = $sum[$c][$d]-$sum[$a-1][$d];
        } else if($a==0 && $b==0) {
            $ans = $sum[$c][$d];
        }
        
        printf("%d\n",$ans);
    }
?>

<?php

list($h, $w, $n) = explode(" ", trim(fgets(STDIN)));

$sum = [[]];

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

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

for ($j = 0; $j < $w; $j++) {

$sum[$i][$j] = $a[$i][$j];

if (0 < $i) $sum[$i][$j] += $sum[$i-1][$j];

if (0 < $j) $sum[$i][$j] += $sum[$i][$j-1];

if (0 < $i && 0 < $j) $sum[$i][$j] -= $sum[$i-1][$j-1];

}

//print_r($sum);

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

list($a, $b, $c, $d) = explode(" ", trim(fgets(STDIN)));

$a--; $b--; $c--; $d--;

if ($a>0 && $b>0) {

$ans = $sum[$c][$d]+$sum[$a-1][$b-1]-$sum[$a-1][$d]-$sum[$c][$b-1];

} else if ($a==0 && $b>0) {

$ans = $sum[$c][$d]-$sum[$c][$b-1];

} else if ($a>0 && $b==0) {

$ans = $sum[$c][$d]-$sum[$a-1][$d];

} else if($a==0 && $b==0) {

$ans = $sum[$c][$d];

}

printf("%d\n",$ans);

}

解答例

カテゴリー