Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-03-26Member SRM465(DIV2)

SRM465 div2 第一問(250点)

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

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

簡単。だけどバブルソート実装してて提出するのが遅くなってしまった。

敗因その一。


短く書き直した。


public class NumberNeighbours {

	public int numPairs(int[] numbers) {
		int length = numbers.length;
		for (int i = 0 ; i < length ; i++) {
			String x = String.valueOf(numbers[i]);
			int xlength = x.length();
			char chars[] = new char[xlength];
			x.getChars(0, x.length(), chars, 0);
			java.util.Arrays.sort(chars);
			numbers[i] = Integer.valueOf(String.copyValueOf(chars));
		}

		int answer = 0;
		for (int i = 0 ; i < length ; i++) {
			for (int j = i + 1 ; j < length ; j++) {
				if (numbers[i] == numbers[j]) {
					answer++;
				}
			}
		}
		return answer;
	}

}

2010-03-17SRM464(DIV2)

SRM464 div2 第一問(250点)

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

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

楽勝。これを早めに出せたのは良かった


public class ColorfulBoxesAndBalls {
	public int getMaximum(int numRed, int numBlue, int onlyRed, int onlyBlue, int bothColors) {
		int max = numRed * onlyRed + numBlue * onlyBlue;
		int n = Math.min(numRed, numBlue);
		if (onlyRed + onlyBlue < bothColors * 2) {
			max += n  * (bothColors * 2 - onlyRed - onlyBlue);
		}
		return max;
	}
}

2010-03-08[過去問]SRM457(DIV2)

SRM457 div2 第一問(250点)

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

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

問題の解釈にやや時間がかかった。

実は行ごとにCの数を数えて、その数を対応する列の下から積み上げればいいと気づいたときは

既に200点を切ってました\(^o^)/


public class TheSquareDivTwo {

	public String[] solve(String[] board) {
		int N = board.length;
		int R[] = new int[N];
		int i = 0;

		// Cを数える
		for (String line : board) {
			for (int j = 0 ; j < line.length() ; j++) {
				if (line.charAt(j) == 'C') {
					R[i]++;
				}
			}
			i++;
		}

		// 下から積み上げるように文字列を生成
		String[] answer = new String[N];
		for (int j = 0 ; j < N ; j++) {
			answer[j] = "";
			for (i = 0 ; i < N ; i++) {
				if (R[i] < N) {
					answer[j] += ".";
					R[i]++;
				} else {
					answer[j] += "C";
				}
			}
		}
		return answer;
	}
}

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

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

}

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

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

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

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

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