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

最短の区間 (paizaランク B 相当)

毎回区間和をループで求めて解くと、計算量が多すぎて、タイムオーバーになります。

そこで、しゃくとり法というアルゴリズムを使います。
しゃくとり法のアルゴリズムの理解は難しくないのですが、
実装が慣れないと難しく感じるので、コードを書いて慣れると良いようです。

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

javascript

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [N, M] = lines[0].split(" ").map(Number);
let sum = 0;//区間和
ans = Infinity;//最短の区間の長さ
let l = 0;//左端
let u = 0;//右端

const A = lines[1].split(" ").map(Number);

sum += A[0];

while (1) {
    if (M <= sum) {
        sum -= A[l];
        ans = Math.min(ans, u-l+1);
        l++;
    }else{ // (sum < M)
        u++;
        if (u === N) {//右端が全区間の右端に到達したら抜ける
            break;
        }else{
            sum += A[u];    
        }
        
    } 
}//while
console.log(ans === Infinity ? -1 : ans);

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

javascript

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [N, M] = lines[0].split(" ").map(Number);
const A = lines[1].split(" ").map(Number);

let sums = [0];//累積和
for (let i = 0; i < N; i++) {
    sums.push(sums[i] + A[i]);
}

let count = Infinity;//最短の区間の長さ
let start = 0;//左端
let end = 0;//右端

while (true) {
    if (end >= N) {//右端がN以上になったら
        break;
    }
    //区間和を累積和で計算
    if (sums[end + 1] - sums[start] >= M) {
        if (end - start + 1 < count) {
            count = end - start + 1;
        }
        start += 1;//左端を進める
    } else {
        end += 1;
    }
}//while
if (count === Infinity) {
    count = -1;//解がないなら-1
}
console.log(count);

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

javascript

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n, m] = lines[0].split(" ").map(Number);
const a = lines[1].split(" ").map(Number);

let [head, tail] = [0, 0];//右端、左端
let [sum, ans] = [0, n + 1];//区間和sum、答えans初期値n+1

while (true) {
    if (sum >= m) {
        ans = Math.min(ans, head - tail);
        sum -= a[tail];
        tail += 1;
    } else {
        if (head === n) {
            break;
        }
        sum += a[head];
        head += 1;
    }
}//while
//条件を満たす部分列がなかった場合
if (ans === n + 1) {
    ans = -1;
}    
console.log(ans);

解答例(累積和)

累積和を導入すれば計算量が落ちて、時間内に処理ができます。

区間和の長さlを最短の1からNまで順に調べていきます。
長さlの区間和を、先頭から順に、累積和で求めます。
S >= Mを満たすlが見つかったら、それが最短の長さなので、lを出力して、処理を終了します。
最後まで見つからなかったら、-1を出力します。

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

//最短の長さが存在するか
let flag = false;

//区間和の長さl,1からNまで、短い方から長くしていく
for (let l = 1; l <= N; l++) {
    //区間和の始まりのインデックス
    for (let j = 0; j <= A.length - l; j++) {
        
        //jからj+l-1の区間和Sを累積和sumsで求める
        let S = sums[j+l] - sums[j];
        
        //区間和Sが M 以上か
        if (S >= M) {
            //長さを出力
            console.log(l);
            //最短の長さが存在したら
            flag = true;
            break;
        }              
    } //forj    
    if (flag) break;//最短の長さが存在したらbreak
} //for l

//そのような部分列が存在しない場合は -1 を出力
if (!flag) console.log(-1);