山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

いもす法

いもす法

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

参考サイト

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]において、積木が取り除かれる(出店処理) に対応します。 いまいち、しっくりきていませんが、同様の問題を解くことで身につくと思います。