1.はじめに

最近AtcoderやAOJを始め、アルゴリズムに関する勉強を始めました。今回は初めて出た競プロの大会でぼこぼこにされた尺取り法についての解説記事になります。私自身図解が最強だと思っているので図解をなるべく多く用いていきたいと思います。ちなみに出てくるコードはJavaで記述したものになります。

2.尺取り法とは

簡単な尺取り法のまとめを書いておきます。

条件を満たすすべての区間の検索に用いる
$O(N^2)$を$O(N)$にできる

後ほど例題を出しますが、そちらも条件を満たす最小の区間を求めよという形式でした。区間って言葉が出てきたら尺取り法を検討するとよいかもしれません。最大の魅力は $O(N^2)$を$O(N)$ にできるという点です。それでは尺取り法についてここから詳しく説明します。

尺取り法は区間の左端と右端を始点から終点まで動かしていくやり方になります。その動きが尺取り虫に似ていることから尺取り法という名前が付けられているそうです。ここで例題としては「次のような数列が与えられたときに、総和が40以上になる最小の区間を求めよ」としてみます。答えは[3,4,5,6,7,8,9]になります。

実行時間を考えないやり方

実行時間を考えないのなら二重for文で回せば全通り試してできると思います。コードにすると以下のようなコードになります。

import java.util.Arrays;

public class example {
    public static void main(String[] args) {
        int[] numbers = {0,1,2,3,4,5,6,7,8,9};
        int sum;
        int min_length = 99999999;
        int[] min_numbers = new int [numbers.length];
        int count = 0;

        for(int left=0;left<numbers.length;left++){
            sum = 0;
            for(int right=left;right<numbers.length;right++){
                count++;
                sum += numbers[right];
                if ((sum >=40) && (min_length > right-left)){
                    min_numbers = Arrays.copyOfRange(numbers, left, right+1);
                    min_length = min_numbers.length;
                } 
            }
        }
        System.out.println(count); //55
        System.out.println(Arrays.toString(min_numbers)); //[3,4,5,6,7,8,9]
   }
}

わかりやすいようにfor文の中身が実行される回数もカウントしています今回では55回for文の中を回していることになります。オーダー数は$(n^2+n)/2$となりオーダー数が$O(n^2)$となっていることがわかります。ちなみにfor文の動きを図解すると以下のようになります。

左端であるleftと右端であるrightを動かして、区間を検索します。leftは左から$n$回動くだけですが、rightはleftに戻って最後まで動くことを繰り返すため、rightの矢印の量が多くなってしまっています。今は配列のサイズが10なのでよいですがこれが競プロでは$2×10^5$とかの大きなサイズになり、繰り返しの回数が膨大な量になってしまうことは明らかです。

尺取り法での解法

同じ問題を尺取り法で解決してみます。尺取り法では以下のようなコードになります。

import java.util.Arrays;

public class Two_Pointer_Approach {
    public static void main(String[] args) {
        int[] numbers = {0,1,2,3,4,5,6,7,8,9};
        int sum = 0;
        int min_length = 99999999;
        int[] min_numbers = new int [numbers.length];
        int count = 0;  
        int right = 0;

        for(int left=0;left<numbers.length;left++){
            count++;

            while(right < numbers.length){
                count++;
                sum += numbers[right];
                right++;

                if ((sum >=40)) break;
            }
            
            if ((min_length > right-left) && (sum >= 40)){
                min_numbers = Arrays.copyOfRange(numbers, left, right);
                min_length = min_numbers.length;
            }

            sum -= numbers[left];
        }
        System.out.println(count); //20
        System.out.println(Arrays.toString(min_numbers)); //[3,4,5,6,7,8,9]
   }
}

先ほどは二重for文で回していましたが、尺取り法ではfor文とwhile文で実行します。条件を満たす区間が見つかるまで右端を右に動かし、条件に合ったところがあれば、右端を固定して左端を右を動かしていきます。こうすることで繰り返しの処理を行う部分が20回まで減っています。このように右端を最初から最後まで動かすのと、左端を最初から最後まで動かすのを行っているため、実行回数は$2n$回になります。個人的にコードを書く際には、右端の変数rightを初期化しないで動かしていくところや、左端を動かすときに合計値から動かした分引いておくという処理を意識すると書きやすかったです。こちらも図解を載せておきます。

今回ではかなり単純な例にしたので、最初の条件の合う区間を探す際にrightが右端まで行っていますが、本来はもう少し複雑な動きをします。でもやることはここに書いてあることと同じで、右端を動かして条件の合う区間を探して、左端を動かしてもまだ条件を満たしてるかなというのを繰り返します。この矢印の動きに注目するとrightもleftもただ左端から右端に動いただけなので、繰り返し回数が2Nになっていることがわかると思います。そんなこんなで、尺取り法はオーダー数を$O(n^2)$から$O(n)$にすることができるというお話でした。

3.尺取り法を使った問題

尺取り法を使った問題を以下に貼っておきます。AOJのサイトでも、Atcoderのサイトの両方を貼っておいたので、お好きな方を解いてみてください。

4.おわりに

今回は尺取り法をなるべく簡単に紹介しました。私自身初投稿ということもあり、あまりうまく書けた気がしませんが、誰かのお力添えになれたなら幸いです。例題はわかりやすくするために自分で考えたものにしましたが、既存のものを用いた方がよさそうですね。これからも備忘録として、アルゴリズムの解説記事を書いていこうと思います。

参考リンク

私より遥かに詳しく解説している記事↓

3.のAtCoderの問題を解説している動画です↓