Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-01-21SRM459(DIV2)

初参戦

15:31 | 初参戦 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - 初参戦 - hama_DU@TopCoderへの道

先日(1/20)行われたTopCoderSRM(Single Round Match)に初参戦しました。

割とお気楽に参加出来るので今後もがんばって続けようと思います。

言語は基本的にjavaで行きます。

SRM459 div2 第一問(250点)

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

http://www.topcoder.com/stat?c=problem_statement&pm=10681&rd=14145

再帰的に生成される画像の、斜線部分の面積を求める問題。

これは割とすぐに出来ました。


public class RecursiveFigures {
	public static double getArea(int sideLength, int K)
	{
		double area = sideLength * sideLength * Math.PI / 4;
		double length = sideLength;
		int i;
		for (i = 1 ; i < K ; i++) {
			length *= (Math.sqrt(2) / 2);
			area -= length * length;
			area += length * length * Math.PI / 4;
		}
		return area;
	}
}

単純に四角形の面積を引きーの、円の面積を足しーの、の繰り返し。

今思うとdo-whileで良かったな、これ。

あと

length *= (Math.sqrt(2) / 2);

の部分は

length /= Math.sqrt(2);

こう書くか、ルート2をあらかじめ与えて

length /= 1.414213562373

て書いた方が良かったね。。。

SRM459 div2 第二問(500点)

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

http://www.topcoder.com/stat?c=problem_statement&pm=10682&rd=14145

整数Xについての不等式が複数提示される。それらの条件を最も多く満たすXが存在するとき、

満たす条件の数を求める問題。

これは時間切れでした。他の人のソースコードを見ると、X を -0.5 ~ 1000.5 の範囲で動かして

同時に満たす条件の数を計算している人が多かったです。シンプルですがその発想はなかった。


僕は各条件について、取りうる X の値を限定していく手法で作ってみました。

例えば、 X >= 5 が与えられたら

X = 5 に合致条件数を 1 プラス。

X = 4 のデータが無かったら作成して合致条件数に 0 を代入。

X > 5 の範囲でデータを探し、見つかったら、合致条件数を 1 プラス。

すべての条件で処理が終わったら、持っているデータのうちで最も合致条件数が多いものを返す。

しかし、どこをどう間違えたのか特定のテストケースに合格せずに失敗しました。

これは後でやりなおします。

SRM459 div2 第三問(1000点)

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

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

時間切れのため、問題を見てすらいません。