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

2022年9月11日

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

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

問題文

H 行 W 列の行列 A の y 行 x 列における累積和 S(y,x) を以下の数式・図の通り定義します。以後 A の y 行 x 列の要素を A[y][x] と表すことにします。

S(y,x) = A[1][1] + A[1][2] + ... + A[1][x] + A[2][1] + ... + A[2][x] + ... + A[y][1] + ... + A[y][x]

H 行 W 列の二次元配列 A と、累積和を求めたい行・列番号についての情報が与えられるので、各ペアについて累積和を求めてください。
例として、入力例 1 の行列における累積和 S(2,2) は次のピンクの部分の和となり、S(2,2) = 12 となります。

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

出力値（例）
1
12
45

解答例

<?php
    list($h, $w, $n) = explode(" ", trim(fgets(STDIN)));
    
    $sRow = array_fill(0, $h+1, 0);
    $s = array_fill(0, $w+1, $sRow);
    
    for ($i=0; $i<$h; $i++) {
        $a[$i] = explode(" ", trim(fgets(STDIN)));
        
        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);
    
    for ($i=0; $i<$n; $i++) {
        list($y, $x) = explode(" ", trim(fgets(STDIN)));
        printf("%d\n", $s[$y][$x]);
    }
?>

<?php

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

$sRow = array_fill(0, $h+1, 0);

$s = array_fill(0, $w+1, $sRow);

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

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

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

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

list($y, $x) = explode(" ", trim(fgets(STDIN)));

printf("%d\n", $s[$y][$x]);

}

解答例

カテゴリー