CODE FESTIVAL 2015 予選B D: マスと駒と色塗り/Squares, Pieces and Coloring

問題

code-festival-2015-qualb.contest.atcoder.jp

解法

塗り終わった区間の[始点, 終点]を保持しおく。塗るときに合併される区間がある場合は合併していけば、保持する情報も少なくて済む。

これのイメージで解いた↓kenkoooo.hatenablog.com

コード

import java.util.ArrayList;
import java.util.Map;
import java.util.Scanner;
import java.util.SortedMap;
import java.util.TreeMap;

public class Main {

    public void solve() {
	Scanner scanner = new Scanner(System.in);
	int N = scanner.nextInt();
	long[] S = new long[N];
	long[] C = new long[N];
	for (int i = 0; i < N; i++) {
	    S[i] = scanner.nextLong();
	    C[i] = scanner.nextLong();
	}
	scanner.close();

	ArrayList<Long> ans = new ArrayList<>();

	// 塗り終わった区間の情報<先頭, 末尾>を保存する
	TreeMap<Long, Long> map = new TreeMap<>();
	map.put(0L, 0L);// floorKeyした時にnullが来ると嫌なので0埋め
	for (int i = 0; i < N; i++) {
	    // スタートが既に塗られていたら、スタート位置をその区間の先頭にする
	    long floorKey = map.floorKey(S[i]);
	    if (map.get(floorKey) >= S[i]) {
		S[i] = floorKey;
	    }

	    long target = S[i] + C[i] - 1;// 行き先
	    ArrayList<Long> willRemove = new ArrayList<>();// 今調べている区間に含まれる区間

	    // スタートより後ろの区間について調べる
	    SortedMap<Long, Long> tail = map.tailMap(S[i]);
	    for (Map.Entry<Long, Long> entry : tail.entrySet()) {
		long start = entry.getKey();
		long end = entry.getValue();

		// 行き先が塗り終わった区間の先頭に被るならその区間を合併していく
		if (start <= target) {
		    target += end - start + 1;
		    willRemove.add(start);
		} else {
		    // かぶらなければ終了
		    break;
		}
	    }

	    // 合併された区間情報は邪魔なので削除する
	    for (long key : willRemove) {
		map.remove(key);
	    }

	    // 新しく出来た区間を保存する
	    map.put(S[i], target);

	    // 答えも記録しておく
	    ans.add(target);
	}

	// 出力
	StringBuilder builder = new StringBuilder();
	for (long target : ans) {
	    builder.append(target + "\n");
	}
	System.out.print(builder.toString());
    }

    public static void main(String[] args) {
	new Main().solve();
    }

}