Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-06-18SRM473(DIV1)

codercoder2010/06/19 06:16>>red pointは普通に計算していくだけ。
ここが線形探索だと計算量的に間に合わないですよ(1000000,100000,0,0,0 とか)

hama_DUhama_DU2010/06/19 18:07ほんとですね!longのキャスト直したらTLEしました!

2010-03-07[過去問]SRM463(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

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

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

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

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


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

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

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の宝庫だったのではないだろうか。

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

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

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

2010-02-14Member SRM461(DIV2)

SRM461 div2 第三問(1000点)

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

http://www.topcoder.com/stat?c=problem_statement&pm=10747&rd=14181

ゲーセンのハイスコアのネームエントリー風に文字を入力するとき、

最小でいくつキー入力が必要かという問題。

残り20分ごろになってOpenはしたが、解くことはできなかった。

tomeruntomerun2010/02/14 16:45550ですが、
> うちのプログラムが出した答えは -1 、つまり埋まらず。正しくは4個全部使えば埋められるらしい。

逆、ではないでしょうか。
円の直径<height のとき、Math.sqrt(r * r - height24) の引数が負になってdistがNaNになってしまうので、以降distとwidthの比較が全部falseになるのではないかと。

hama_DUhama_DU2010/02/14 21:14tomerun様
コメント・ご指摘ありがとうございます。

>逆、ではないでしょうか。
先ほど確認したところ、見間違いで-1の方が正しいようです。

>円の直径<height のとき・・・
そうですね!その場合を忘れてました!
あとでソースコードを書き直してみます!