paizaラーニング レベルアップ問題集 Aランクレベルアップメニュー JavaScript 区間和の計算

区間和の計算 (paizaランク B 相当)

普通に解くと、

タイムオーバー

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//要素数N
const N = Number(lines[0]);
//数列A
const A = lines[1].split(" ").map(num => Number(num));
//クエリの数 n 
const n = Number(lines[2]);


//クエリについて
for (let i = 1; i <= n; i++) {
    //整数 l , u が与えられるので、
    const [l,u] = lines[2 + i].split(" ").map(num => Number(num));
    //A_l から A_u までの総和 S_i を出力
    let S = 0;
    for (let j = l; j <= u; j++) {
        S += A[j];
    }
    console.log(S);
}

のようになりますが、これだとクリエごとに毎回ループで計算するので、計算量が多すぎて、タイムオーバーになります。

前処理で累積和を作成し、その後、クエリに答えていきます。

累積和の作成方法や、クエリの答え方はいろいろあるので、理解しやすいものや、しっくりくるものを参考にしていただけたらと思います。

解答例

累積和Sの初期値を配列に0を入れた[0]を用意し、S[i + 1] = S[i] + A[i]で、代入していきます。
クエリの答え方はS[u + 1] - S[l]です。
S[u+1]= 0+a[0]+...+a[l-1]+a[l]+a[l+1]+...+a[u]
S[l] = 0+a[0]+...+a[l-1]
S[u+1]-S[l] = a[l]+...+a[u]

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//要素数N
const N = Number(lines[0]);
//数列A
const A = lines[1].split(" ").map(num => Number(num));
//累積和
let S = [0];
for (let i = 0; i < N; i++) {
    S[i + 1] = S[i] + A[i];
}

//クエリの数 n 
const n = Number(lines[2]);
//クエリに答える
for (let i = 1; i <= n; i++) {
    const [l, u] = lines[i + 2].split(" ").map(Number);
    console.log(S[u + 1] - S[l]);
}

解答例(C++の場合を参考に)

累積和sumの入れ物[0,0,...,0]を作り、sum[i + 1] = sum[i] + A[i]で代入していきます。

javascript

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//要素数N
const N = Number(lines[0]);
//数列A
const A = lines[1].split(" ").map(Number);
//クエリの数 n 
const n = Number(lines[2]);

//累積和
let sum = Array(N + 1).fill(0);
for (let i = 0; i < N; i++) {
    sum[i + 1] = sum[i] + A[i];
}
//クエリに答える
for (let i = 1; i <= n; i++) {
    const [l, u] = lines[i + 2].split(" ").map(Number);
    console.log(sum[u + 1] - sum[l]);
}

解答例(Python3の場合を参考に)

累積和の初期値に配列に0を入れた[0]を用意し、pushでsum[i] + numbers[i]を入れていきます。

javascript

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//要素数N
const N = Number(lines[0]);
//数列A
const numbers = lines[1].split(" ").map(Number);
//クエリの数 n 
const n = Number(lines[2]);

//累積和
let sums = [0];
for (let i = 0; i < N; i++) {
    sums.push(sum[i] + numbers[i]);
}
//クエリに答える
for (let i = 1; i <= n; i++) {
    const [l_i, u_i] = lines[i + 2].split(" ").map(Number);
    console.log(sum[u_i + 1] - sum[l_i]);
}

解答例(Ruby の場合を参考に)

累積和の要素の先頭が0でないつくりかたです。
累積和の入れ物Array(n)をsumで用意し、中身の累積和の要素xの初期値を0とします。
i=0からi=n-1まで、xに数列Aの1要素a[i]を足し、入れ物sumにxを代入する、を繰り返します。
できた累積和の要素は例えば次のとおりです。先頭が0ではないです。
sum[u] = a[0]+...+a[l-1]+a[l]+a[l+1]+...+a[u]

累積和の要素の先頭が0でないので、クエリの答え方も、
sum[u]-sum[l]+a[l]となります。

sum[u]= a[0]+...+a[l]+a[l+1]+...+a[u]
sum[l]= a[0]+...+a[l]
sum[u]-sum[l] = a[l+1]+...+a[u]
sum[u]-sum[l]+a[l] = a[l]+a[l+1]+...+a[u]

また、sum[u]-sum[l-1]=a[l]+a[l+1]+...+a[u]とできそうですが、sum[l-1]が、l=0の時sum[-1]=undefinedなので、できません。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//要素数N
const n = Number(lines[0]);
//数列A
const a = lines[1].split(" ").map(Number);

//累積和
let x = 0;
let sum = Array(n);
for (let i = 0; i < n; i++) {
    x += a[i];
    sum[i] = x;
}

//クエリの数 q 
const q = Number(lines[2]);
//クエリに答える
for (let i = 1; i <= q; i++) {
    const [l, u] = lines[i + 2].split(" ").map(Number);
    console.log(sum[u] - sum[l] + a[l]);//sum[l]でa[l]を引いているので、a[l]を足す
}