Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-03-07[過去問]SRM463(DIV2)

Practice Roomでシステムテストが試せることに気づく。

部屋に入って、Practice Options > Run System Test で実行できます。

コメントくださった方ありがとう。

SRM463 div2 第一問(250点)

| SRM463 div2 第一問(250点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM463 div2 第一問(250点) - hama_DU@TopCoderへの道

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

簡単。


public class BunnyPuzzle {
	public int theCount(int[] bunnies) {
		int bunnyNum = bunnies.length;
		int count = 0;
		for (int i = 0 ; i < bunnyNum ; i++) {
			// 左端のバニーちゃんは左に飛べないので無視
			if (i > 0) {
				// 左から2番目のバニーちゃんは必ず左に飛べる。
				// それ以外は自分の2つ隣のバニーちゃんを飛び越さないかチェックする
				if (i > 1) {
					int to = bunnies[i - 1] - (bunnies[i] - bunnies[i - 1]);
					if (bunnies[i - 2] < to) {
						count++;
					}
				} else {
					count++;
				}
			}

			// 右端のバニーちゃんは右に飛べないので無視
			if (i < bunnyNum - 1) {
				// 右から2番目のバニーちゃんは必ず右に飛べる。
				// それ以外は自分の2つ隣のバニーちゃんを飛び越さないかチェックする
				if (i < bunnyNum - 2) {
					int to = bunnies[i + 1] + (bunnies[i + 1] - bunnies[i]);
					if (to < bunnies[i + 2]) {
						count++;
					}
				} else {
					count++;
				}
			}
		}
		return count;
	}

}

SRM463 div2 第二問(500点)

| SRM463 div2 第二問(500点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM463 div2 第二問(500点) - hama_DU@TopCoderへの道

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

順列の問題。

つけられる番号が小さい順に並び替えて、かけていくだけ。


public class RabbitNumbering {
	public int theCount(int[] maxNumber) {
		long count = 1;
		long mod = 1000000007;
		int bunnyNum = maxNumber.length;
		java.util.Arrays.sort(maxNumber);
		for (int i = 0; i < bunnyNum; i++) {
			count = (count * (maxNumber[i] - i)) % mod;
		}
		return (int) (count % mod);
	}
}

SRM462 div2 第三問(1000点)

| SRM462 div2 第三問(1000点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM462 div2 第三問(1000点) - hama_DU@TopCoderへの道

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

前回のソースコードを改変。

途中でゴールしてしまう場合のスコアのチェックを行うようにしました。

これで時間させかければ解けるようにはなったのですが

まだ最悪ケースで落とされます。根本的なアプローチに問題があるような気がします。


public class SteeplechaseTrack {
	// 障害iから障害jへ行き、障害jを超える大変さを求める。
	// iからjへ行くことが不可能な場合-1を返す。
	public static int cost(int i, int j, String[] fences, String[] tracks) {
		int to = tracks[i].charAt(j) - 48;
		if (to == 0) {
			return -1;
		}
		return to + fences[j].charAt(0) - 48;
	}

	// Nは残りの超えるべき障害の数
	// nowは現在どの障害物にいるか、complは現時点での大変さ
	public static int calc(String[] fences, String[] tracks, int N, int now, int compl) {
		if (N == 0) {
			int fin = fences[now].charAt(2) - 48;
			if (fin == 0) {
				// ゴールに行くことが不可能だった
				return -1;
			}
			// 現在の大変さとゴールまでの距離を加える
			return fin + compl;
		}

		int fencesNum = fences.length;
		int max = -1;
		for (int i = 0 ; i < fencesNum ; i++) {
			int to = cost(now, i, fences, tracks);
			if (to == -1) {
				// この障害物には到達不可
				continue;
			}

			int calc = calc(fences, tracks, N - 1, i, compl + to);
			if (calc == -1) {
				// このルートではゴールに到達できない。
				continue;
			}
			to += calc;
			if (max < calc) {
				max = calc;
			}
		}

		// 障害をこれ以上飛ばずに現時点でゴールする場合を考慮
		int fin = fences[now].charAt(2) - 48;
		if (fin != 0) {
			fin += compl;
			if (max < fin) {
				max = fin;
			}
		}
		return max;
	}

	public int maxComplexity(String[] fences, String[] tracks, int N) {
		int max = -1;
		int fencesNum = fences.length;
		for (int i = 0 ; i < fencesNum ; i++) {
			int to = fences[i].charAt(1) - 48;
			if (to != 0) {
				int compl = 0;
				compl = calc(fences, tracks, N - 1, i, to + fences[i].charAt(0) - 48);
				if (compl > max) {
					max = compl;
				}
			}
		}
		return max;
	}
}