[Aizu Online Judge] Data Sets and Queries 3、しゃくとり法 [DSL3] - ヤマカサのプログラミング勉強日記

しゃくとり法

今回はしゃくとり法について勉強しました。

しゃくとり法は連続する区間に対するクエリを効率的に返します。

Sliding Window - The Smallest Window I (DSL3-A)

The Smallest Window | Sliding Window | Aizu Online Judge

しゃくとり法の考えに従い、数列の和を計算していきます。和を計算していくなかで、初めて和が $S$ 以上となる区間が最小値の候補となります。

コード

import java.util.Scanner;

public class ProblemA {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int S = scan.nextInt();
        long[]a = new long[N];
        for(int i = 0; i < N; i++) {
            a[i] = scan.nextLong();
        }
        scan.close();
        int min = Integer.MAX_VALUE;
        long sum = 0;
        int right = 0;
        for(int left = 0; left < N; left++) {
            while(right < N && sum + a[right] < S){
                sum += a[right];
                right++;
            }
            if(right < N) {
                if(sum + a[right] >= S) {
                    int l = right - left + 1;
                    min = Math.min(min, l);
                }
            }
            if(right == left) {
                right ++;
            }else {
                sum -= a[left];
            }
        }
        if(min == Integer.MAX_VALUE) {
            System.out.println(0);
        }else {
            System.out.println(min);
        }
    }
}

Sliding Window - The Smallest Window II (DSL3-B)

The Smallest Window II | Aizu Online Judge

マップを用いて $K$ 以下の数字をキーとして値をそのキーの個数として管理します。

あるキーが消えるタイミングでその値が $1$ のときMapからそのキーを消します。

そして、Mapのサイズが $K$ となるタイミングで最小値を更新します。

コード

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int K = scan.nextInt();
        int[]a = new int[N];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < N; i++) {
            a[i] = scan.nextInt();
        }
        scan.close();
        int min = Integer.MAX_VALUE;
        int right = 0;
        for(int left = 0; left < N; left++) {
            while(right < N && map.size() < K) {
                if(a[right] <= K) {
                    map.merge(a[right], 1, (val1, val2) -> val1 + val2);
                }
                right++;
            }
            if(map.size() == K) {
                int l = right - left;
                min = Math.min(min, l);
            }
            if(right == left) {
                right ++;
            }else {
                if(a[left] <= K) {
                    if(map.get(a[left]) == 1) {
                        map.remove(a[left]);
                    }else {
                        map.merge(a[left], -1, (val1, val2) -> val1 + val2);
                    }
                }
            }
        }
        if(min == Integer.MAX_VALUE) {
            System.out.println(0);
        }else {
            System.out.println(min);
        }
    }
}

Sliding Window - The Number of Windows (DSL3-C)

The Number of Windows | Sliding Window | Aizu Online Judge

上記の記事に詳しい解説が載っています。

コード

import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int Q = scan.nextInt();
        long[]a = new long[N];
        long[]x = new long[Q];
        for(int i = 0; i < N; i++) {
            a[i] = scan.nextLong();
        }
        for(int i = 0; i < Q; i++) {
            x[i] = scan.nextLong();
        }
        scan.close();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < Q; i++) {
            long cnt = 0;
            long sum = 0;
            int right = 0;
            for(int left = 0; left < N; left++) {
                while(right < N && sum + a[right] <= x[i]) {
                    sum += a[right];
                    right++;
                }
                cnt += (right - left);
                if(left == right) {
                    right++;
                }else {
                    sum -= a[left];
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.print(sb.toString());
    }
}

Sliding Window - Sliding Minimum Elements (DSL3-D)

Sliding Minimum Elements | Aizu Online Judge

Mapを使って解いたので、しゃくとり法で解いてないのかな？

区間 $L$ に含まれる数字をTreeMapを用いて管理します。firstKey()はその区間の最小値となります。

コード

import java.util.Scanner;
import java.util.TreeMap;

public class ProblemD {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int L = scan.nextInt();
        int[]a = new int[N];
        TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
        for(int i = 0; i < N; i++) {
            a[i] = scan.nextInt();
        }
        scan.close();
        for(int i = 0; i < L; i++) {
            map.merge(a[i], 1, (val1, val2) -> val1 + val2);
        }
        int min = map.firstKey();
        StringBuilder sb = new StringBuilder();
        sb.append(min);
        for(int i = L; i < N; i++) {
            if(map.get(a[i - L]) == 1) {
                map.remove(a[i - L]);
            }else {
                map.merge(a[i - L], -1, (val1, val2) -> val1 + val2);
            }
            map.merge(a[i], 1, (val1, val2) -> val1 + val2);
            sb.append(" ").append(map.firstKey());
        }
        System.out.println(sb.toString());
    }
}

感想

しゃくとり法の考え方を少し理解した気がします。問題によってしゃくとり法の中身の部分を考える必要がありますね。