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

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

        // 現在の右端を表す変数 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();
        }

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

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 未満の区間の個数を求めてください。
入力を受け取るコードがすでに用意されているので、コードを書き足してプログラムを完成させてください。

入力される値

5 5
1 1 5 5 1

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

期待する出力値

Tips

動画へ戻る

次のチャプターへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃08:しゃくとり法

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

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

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

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

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

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

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

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

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

ログインすると採点できます

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：

5 5
1 1 5 5 1