新・アルゴリズムとデータ構造入門 Java編8:しゃくとり法

#08:しゃくとり法

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, k;
        n = sc.nextInt();
        k = sc.nextInt();

        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // 現在の右端を表す変数 r, 現在の総和を表す変数 sum, 答えを表す変数 count を 0 で初期化
        // 左端 l を 0 から n - 1 まで繰り返す

        // r が n より小さく、sum に a[r] を加えても k を超えない間
        // sum に a[r] を加えて右端 r を 1 ずつ増やす
        // r - l を count に加える

        // もし l が r と同じなら
        // r を 1 増やす
        // そうでなければ
        // sum から a[l] を引く

        // count を出力
    }
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, k;
        n = sc.nextInt();
        k = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // ここにコードを書く
    }
}

この動画を見るにはpaiza会員登録のうえ
有料会員登録が必要です

無料会員登録して始める

★ 実技1

実技課題「しゃくとり法の実装」

整数 n, k と長さ n の配列 a が与えられます。
この配列の中で、総和が k 未満の区間の個数を求めてください。
入力を受け取るコードがすでに用意されているので、コードを書き足してプログラムを完成させてください。

【制約】
・入力は全て整数
・ 1 ≦ n ≦ 10
・ 1 ≦ (配列 a の各要素), k ≦ 100

入力される値

5 5
1 1 5 5 1

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

高速に探索を行うアルゴリズムである「しゃくとり法」について学習します。

しゃくとり法が使える条件

しゃくとり法を適用するための条件には、いくつかの制約があります。これらの制約を満たしていれば、必ずしゃくとり法を適用することができます。

・ある区間が条件を満たすなら、その区間に含まれるすべての区間が条件を満たす
・ある区間が条件を満たさないなら、その区間を含むすべての区間が条件を満たさない
・左端や右端を 1 つ動かしたとき、条件を満たすかどうかの判定を高速に行うことができる

しゃくとり法の l, r が表す区間

しゃくとり法の l, r が表す区間は、半開区間 [l, r) になります。

しゃくとり法の時間計算量

条件判定にかかる時間計算量が O(x) のとき、しゃくとり法の全体での時間計算量は、O(nx) となります。
これは、ループに必要な回数が n であり、また右端を伸ばす回数の合計も n であることによります。

有料プランで現役エンジニアに相談可能！

プログラミング学習 > Java > 新・アルゴリズムとデータ構造入門 Java編 > 新・アルゴリズムとデータ構造入門 Java編8: 累積和 > しゃくとり法

実行する

採点する

入力
出力
コンパイルエラー
実行時エラー

出力タイプ：

5 5
1 1 5 5 1