Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-03-04[過去問]SRM462(DIV2)

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

障害物レース問題。

障害が複数あって、障害の難しさ、スタート⇔障害、障害⇔ゴール、障害⇔障害の距離があらかじめ決められているとき、

一番クリアするのが大変なコースを求めてその大変さ(=総走行距離と超えた障害の難しさの和)を出す問題。

むっ、これは簡単なのでは!?


とりあえず速度とか気にしないで書いたのがこちら。

でもTOPの方のコードもこんな感じだったのでsystem testにはたぶん通るかと思います。

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;
			}
		}
		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;
				for (int x = N ; x >= 1 ; x--) {
					// N個の障害を超えてゴールできない場合は、Nをひとつ減らして再探索
					// ひょっとしたらここら辺最悪ケースで落ちるかも。
					compl = calc(fences, tracks, x - 1, i, to + fences[i].charAt(0) - 48);
					if (compl != -1) {
						break;
					}
				}
				if (compl > max) {
					max = compl;
				}
			}
		}
		return max;
	}
}

とりあえず、第三問がはじめて解けました!

ll2010/03/05 06:37プラクティスルームでシステムテスト試せますよ
たぶん1000点問題はそれだとシステムテストで落とされると思います

hama_DUhama_DU2010/03/05 07:59>システムテスト試せますよ
そうなんですか!?今度試してみます!

>それだとシステムテストで落とされると思います
む~ やはりN個設置不可の場合はもう一工夫する必要がありますね。