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

2022年8月29日

【クエリメニュー】> 【平方分割】STEP: 1 累積和 (paizaランク C 相当) [難易度: 1753 ±26]

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

問題文

長さ N の数列 A と、K 個の整数 Q_1 ... Q_K が与えられるので、各整数 Q_i (1 ≦ i ≦ K) について A_1 ... A_{Q_i} の和を求めてください。

入力値（例）
3 1
69
12
28
3

出力値（例）
109

解答例

<?php
    list($n, $k) = explode(" ", trim(fgets(STDIN)));
    
    $ans = [];
    
    for ($i = 0; $i < $n; $i++) {
        $a[$i] = trim(fgets(STDIN));
        
        if ($i == 0) {
            $ans[$i] = $a[$i];

        } else {
            $ans[$i] = $ans[$i-1] + $a[$i];
        }
    }
    //print_r($ans);
    
    for ($i = 0; $i < $k; $i++) {
        $q = trim(fgets(STDIN));
        echo $ans[$q-1]. "\n";
    }
?>

<?php

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

$ans = [];

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

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

if ($i == 0) {

$ans[$i] = $a[$i];

} else {

$ans[$i] = $ans[$i-1] + $a[$i];

}

//print_r($ans);

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

$q = trim(fgets(STDIN));

echo $ans[$q-1]. "\n";

}

解説

長さNの数列AとK行の整数Qが与えられ、数列Aの最初から整数Qまで合計を出力する問題。
入力値（例）の例でいうと、整数Qが2だった場合は、数列Aの1番目の69と数列Aの2番目の12で69+12=81になります。

まず、数列Aを受け取ったとき、iが0の場合（一番初めの数値）は配列ansに格納します。次からの数列Aは、[i-1]、つまり前の配列に足して格納します。

ans[0]	69	69
ans[1]	12	ans[1-1](69)+a[1](12)=81
ans[2]	28	ans[2-1](81)+a[2](28)=109

配列ansにすでに合計した値が入っているので、整数Qを受け取ったら、そのまま配列ans[Q]で出力します。

整数Qを受け取ってから、A_1からA_Qまでの和をいちいち計算していたらタイムオーバーになってしまいました。この問題で累積和の意味が少し分かりました。(*'ω'*)

解答例

解説

カテゴリー