Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-07SRM387 (Practice)

SRM 387 IntervalSubsets

|  SRM 387 IntervalSubsets - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 387 IntervalSubsets - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8084

  • 方針を検討
    • DPっぽい
    • startとfinishが100以下なのがポイントになりそうだ
    • とりあえず区間の昇順にソートしておく。
  • 状態を考える
    • 今考えている区間と、最後に使った区間とで状態を持つのはどうか
    • 状態遷移は、最後に使った区間(の終わり)に交わらない区間を選択していく。
      • でもこれだけだと複数の区間を飛び越えて選択してしまいそうだ。これをどう処理しよう・・・
  • 発想を変えてみる
    • グラフに落としこんでみる
      • 各区間をノードとして、区間が交わっていればノードをエッジでつなぐ
    • 頂点彩色問題っぽい?
      • 効率的な解き方あったっけ
  • 時間切れ。

その後

  • 他の人のコードを見るといろんな解き方があって面白い。
    • グラフで考えてる人もいる
  • DP解はこれ以上区間を選択できなかったら答えを足し算する
    • 当たり前のようだがその発想には至らなかった・・・
import java.util.Arrays;
import java.util.Comparator;

public class IntervalSubsets {
	class Data {
		int from;
		int to;
		Data(int f, int t) {
			from = f;
			to = t;
		}
	}

	public int numberOfSubsets(int[] start, int[] finish) {
		int len = start.length;
		if (len == 1) {
			return 1;
		}
		
		Data[] datas = new Data[len];
		for (int i = 0 ; i < len ; i++) {
			datas[i] = new Data(start[i], finish[i]);
		}
		
		int[] dp = new int[101];
		dp[0] = 1;
		int ans = 0;
		for (int i = 0 ; i < 101 ; i++) {
			int toward = 200;
			for (int j = 0 ; j < len ; j++) {
				if (i < datas[j].from) {
					toward = Math.min(toward, datas[j].to);
				}
			}
			if (toward == 200) {
				ans += dp[i];
			} else {
				for (int j = 0 ; j < len ; j++) {
					if (i < datas[j].from && datas[j].from <= toward) {
						dp[datas[j].to] += dp[i];
					}
				}
			}
		}
		return ans;
	}
}