Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-07SRM387 (Practice)

500が正解率4割あるのに解けなかった 193/439位

問題結果ポイントその他
300MarblesRegroupingEasyAccepted233.62貪欲法
500IntervalSubsetsOpened0.00DP?
950StrangeArrayUnopened0.00読んでない

SRM 387 MarblesRegroupingEasy

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

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

  • 方針を検討
    • joker boxを決め打ちして探索
    • joker box以外で2種類以上のmarbleが入っていたらjoker boxに突っ込む
    • marbleが1種類だけならその種類ごとにカウント
    • カウントが2以上なら(カウント - 1)をjoker boxに突っ込む

public class MarblesRegroupingEasy {

	public int minMoves(String[] boxes) {
		int bl = boxes.length;
		int cl = boxes[0].length();
		int minMove = Integer.MAX_VALUE;
		for (int jb = 0 ; jb < bl ; jb++) {
			int mustMove = 0;
			int[] coltomove = new int[cl];
			for (int b = 0 ; b < bl ; b++) {
				if (b == jb) {
					continue;
				}
				int cnt = 0;
				int col = -1;
				for (int c = 0 ; c < cl ; c++) {
					if (boxes[b].charAt(c) >= '1')  {
						cnt++;
						col = c;
					}
				}
				if (cnt >= 2) {
					mustMove++;
				} else if (cnt == 1) {
					coltomove[col]++;
				}
			}
			for (int c = 0 ; c < cl ; c++) {
				if (coltomove[c] >= 2) {
					mustMove += coltomove[c] - 1;
				}
			}
			minMove = Math.min(minMove, mustMove);
		}
		return minMove;
	}
}

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;
	}
}