Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

それじゃ今日も行ってみよー

1月18日に行われたSRM462にチャレンジします。

SRM462 div2 第一問(250点)

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

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

半径が等倍で構成される同心円上の複数の円をターゲットとみなし矢を射る時、

得点の期待値を求める問題。(円ごとに点数が設定されている)

なお、どの円にあたるかどうかはランダム(運次第)


問題を理解するのに少し時間がかかったが、

面積比が1:3:5:7: ... :2n-1 になることが分かれば簡単だった。

public class Archery {
	public double expectedPoints(int N, int[] ringPoints) {
		double point = 0.0f;
		// 面積の係数
		int k = 1;
		for (int i = 0 ; i <= N ; i++) {
			point += k * ringPoints[i];
			k += 2;
		}
		// 全体の面積で割る
		return point / (N + 1) / (N + 1) / 1.0f;
	}
}

SRM462 div2 第二問(500点)

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

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

二種類のローソクをビットに見立て、

n進法でちょうどx歳になるようにしたい。

そのときのnを求める問題。(nは小数でもおk)


これって、方程式を解く問題に帰着できるけどやり方がよく分からない・・・

とりあえずやってみたこと。

  • 計算結果と目的値の大小関係から二分探索的な感じで数値を絞り込んでいく方法。
  • 整数から探してダメだったら、次は2乗根、3乗根・・・と延々とやっていく

どちらも答えがあわず、しかたないので後回し。

てか正解率3.6%って・・・これは間違いなく地雷。Challengeの宝庫だったのではないだろうか。

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個設置不可の場合はもう一工夫する必要がありますね。