記事の概要

自分の勉強兼メモでまとめている記事シリーズです。第六弾。
今までの記事はこちら。

#	記事
5	javaでアルゴリズム入門 - 累積和
4	javaでアルゴリズム入門 - 探索編（bit全探索）
3	javaでアルゴリズム入門 - 探索編（幅優先探索）
2	javaでアルゴリズム入門 - 探索編（深さ優先探索）
1	javaでアルゴリズム入門 - 探索編（全探索、二分探索）

今回の記事では

しゃくとり法

について勉強します。
累積和と一緒に？使われるやつなのですかね。良くセットで紹介されているのを目にします。

しゃくとり法

累積和と同様、数値の配列に対しての操作を早くする技法のようです。

参考：【累積和、しゃくとり法】初級者でも解るアルゴリズム図解

まぁ・・・ぶっちゃけリンク先見ればわかるやろ的なところではありますがね。。。自分の勉強のため一応説明してみますね。

例として、サイズnの整数配列を考えます。
そこから指定された区間の長さtに分割したとき、その区間内での和の最大値はなにになるでしょう？的な問題を解く問題です。
累積和でもできる問題ですね。前回の記事もご覧ください。

例として、サイズ5(n = 5)、区間の長さ2(t = 2)のときを考えます。

図の通りの配列を考えます。
これを区間の長さ2で分割すると以下のようになりますね。

結論からいうと4,5番目を選んだ際の和の4 + 10 = 14が最高値なのですが、ここまでの計算量はいかほどでしょうか。

どの区間を選択するか
その区間内での和の計算

にわけて考えてみましょう。

まずは１.区間の分け方ですが、簡単ですね。
上の例だと4回、和をとっています。
計算式に落とすと、 n - t + 1 回となります。今回は 5 - 2 + 1 = 4回。

次は2. その区間内での和の計算ですが、配列の各要素にアクセスするためにそれぞれ2回ずつ、処理を行っています。

総じて ( n - t + 1 ) * t 回となります。
tをnに依存してとったらO(n^2)くらいの計算量になってしまうので注意しましょう。
これだとnを10^5とかでとってしまうと、ものすごい時間がかかってしまいますね。
そんなときにしゃくとり法の登場です。

まぁ割と簡単な話なのですが・・・
和を覚えておいて、毎回1から足算しないで良いようにしようね。ということです。
以下の図を参照して下さい。

なんとなくわかりますかね。
和を覚えておいて、一回一回全ての要素をt回足さなくて良いようになってます。
計算量は、配列の各要素にアクセスする必要がなくなったので、 n - t + 1回となります。
O(n)と表せると思います。

では例題にいきましょう。

例題

例：AtCoder - abc032-c「列」

問題文・入力例などはここをクリックして表示
　※できるだけ問題リンクを参照してください

（セクション開始）
【問題文】
長さ N の非負整数列 S=s1,s2,...,sN と整数 K があります。あなたの仕事は、以下の条件を満たす S の連続する部分列のうち、最も長いものの長さを求めることです。部分列の長さは 1 以上の列でないといけません。

・その部分列に含まれる全ての要素の値の積は、K 以下である。

もし条件を満たす部分列が一つも存在しないときは、0 を出力してください。

【入力】
入力は以下の形式で標準入力から与えられる。

N K
s1 
s2
:
sN

・1 行目には、数列の長さを表す整数 N(1≦N≦105) と問題文中の整数 K(0≦K≦10^9) が空白区切りで与えられる。
・2 行目からの N 行には、数列の各要素の値が与えられる。そのうち i(1≦i≦N) 行目には、si(0≦si≦10^9) が書かれている。

【出力】
出力は以下の形式で標準出力に行うこと。
1 行目に、含まれる全ての要素の値の積が K 以下となる連続する部分列のうち最長のものの長さを出力せよ。もし条件を満たす部分列が一つも存在しないときは、0 を出力せよ。末尾の改行を忘れないこと。

（セクション終了）

こんな問題です。
ちょっと応用入ってます。
基本的にはしゃくとり法なのですが、今回は長さが決まっていません。
次の方針で実装します。

しゃくとり法の要領で、積を保存しておく。
条件を満たす限り、右端を進める。
条件を満たさなくなったら、左端を進める。
左端が一番右まで来たら、探索終了。その時点での最長の値を出力する。

以下が回答例です。

Main.java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 非負整数列の長さ
        long k = sc.nextLong(); // 積の最大値

        long[] s = new long[n]; // 非負整数列

        for (int i = 0; i < n; i++) {
            s[i] = sc.nextLong();
            if (s[i] == 0l) {
                System.out.println(n);
                return;
            }
        }

        long seki = 1; // 積を保存している変数
        int ans = 0; // 長さの最大値
        int ans_max = -1; // 答えを保存
        int left = 0; // 左端
        int right = 0; // 右端

        for (left = 0; left < n; left++) {

            // 左端を固定し、行けるところまで右端を動かして掛け算する
            while (right < n && seki * s[right] <= k) {
                seki *= s[right++];
            }

            // ansの最大値の保管
            ans = right - left;
            if (ans_max < ans) {
                ans_max = ans;
            }

            // 左端を動かす。left == rightとなるときに注意。
            if (left == right) {
                right++;
            } else {
                seki /= s[left];
            }

        }

        System.out.println(ans_max);
    }
}

はい。いろいろなソースを参照しましたが、なかなか難しかった。。
leftがrightに追いつく例が特に難しかったです。
これも練習が必要そうですね。。。
しっかり練習していきましょう。ソースを何度も読み返そうと思います。

ではまた！

javaでアルゴリズム入門 - しゃくとり法

記事の概要

しゃくとり法

例題