いもす法

いもす法

いもす法なるアルゴリズムを勉強しました。 いもす法は累積和の拡張によるアルゴリズムだそうです。

参考サイト

Imos法(いもす法) - sataniC++

いもす法 - いもす研 (imos laboratory)

問題

Imos法(いもす法) - sataniC++

上記のサイトで紹介されている積木の問題を解いてみました。

コード

import java.util.Arrays;
import java.util.Scanner;

public class Imos {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        String[] str = new String[N];
        int []P = new int[N];
        int []L = new int[N];
        for(int i = 0; i < 2 * N; i++){
            int k = scanner.nextInt();
            if(i % 2 == 0) {
                P[i/2] = k;
            }else if(i % 2 == 1){
                L[i/2] = k;
            }
        }
        scanner.close();
        int sum[] = new int[10];
        int sub[] = new int[10];
        Arrays.fill(sum, 0);
        Arrays.fill(sub, 0);
        for(int i = 0; i < 5; i++) {
            sum[P[i]] ++;
            sum[P[i] + L[i]] --;
        }
        for(int i = 1; i < 10; i++) {
            sum[i] += sum[i-1];
        }
        for(int i = 0; i < 10; i++) {
            System.out.println(sum[i]);
        }
    }
}

sum[P[i]] ++ で座標P[i]において、積木が積み上げられ（入店処理） sum[P[i] + L[i]]-- で座標P[i] + L[i]において、積木が取り除かれる(出店処理) に対応します。 いまいち、しっくりきていませんが、同様の問題を解くことで身につくと思います。