Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-02-14Member SRM461(DIV2)

SRM461 div2 第一問(250点)

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

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


public class TrappingRabbit { 
  public int findMinimumTime(int[] trapX, int[] trapY) { 
    int trapNum = trapX.length; 
    int min = -1; 
    for (int i = 0 ; i < trapNum ; i++) { 
      int sec = (trapX[i] - 1) + (trapY[i] - 1); 
      if (min == -1 || min > sec) {
        min = sec;
      }
    }
    return min; 
  }
}

Challengeで一人撃墜できた。

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 のとき・・・
そうですね!その場合を忘れてました!
あとでソースコードを書き直してみます!

2010-02-13[過去問]Member SRM458(DIV2)

SRM458 div2 第一問(250点)

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

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

砂漠化の問題。


文字列のx番目を文字cに置き換える関数の自作が必要だったのを除けば、

特に工夫はしていません。あと、砂漠のマス目数が変わらなかったら処理を打ち切るなど。

public class Desertification {

	// 文字列のx番目を文字cに置き換え
	public static String setChar(String line, int x, char c) {
		return line.substring(0, x) + String.valueOf(c) + line.substring(x + 1);
	}

	public int desertArea(String[] island, int T) {
		int desertCells = 0, prev_desertCells = 0;
		int islandx = island[0].length(), islandy = island.length;

		String[] island_back = island.clone();
		for (int t = 0 ; t < T ; t++) {
			desertCells = 0;
			for (int y = 0 ; y < islandy ; y++) {
				for (int x = 0 ; x < islandx ; x++) {
					if (island[y].charAt(x) == 'F') {
						try {
							if (island[y-1].charAt(x) == 'D') {
								island_back[y] = setChar(island_back[y], x, 'D');
								desertCells++;
								continue;
							}
						} catch (Exception e) {}

						try {
							if (island[y].charAt(x-1) == 'D') {
								island_back[y] = setChar(island_back[y], x, 'D');
								desertCells++;
								continue;
							}
						} catch (Exception e) {}

						try {
							if (island[y].charAt(x+1) == 'D') {
								island_back[y] = setChar(island_back[y], x, 'D');
								desertCells++;
								continue;
							}
						} catch (Exception e) {}

						try {
							if (island[y+1].charAt(x) == 'D') {
								island_back[y] = setChar(island_back[y], x, 'D');
								desertCells++;
								continue;
							}
						} catch (Exception e) {}
					} else {
						desertCells++;
					}
				}
			}
			island = island_back.clone();
			if (prev_desertCells == desertCells) {
				break;
			}
			prev_desertCells = desertCells;
		}
		return desertCells;
	}
}

例外って便利ですね。

2010-02-11SRM460(DIV2)

SRM460 div2 第一問(250点)

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

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

「Yes」「No」で答えられる質問が複数あり、考えられる答えの組み合わせの数を求める問題。

質問には同じものが含まれることがあり、それらはひとつの質問として考える。

つまり、(組み合わせの数) = 2 ^ (質問の種類) を求める問題である。


楽勝。

import java.util.HashMap;

public class TheQuestionsAndAnswersDivTwo {
	public int find(String[] questions) {
		int questionsnum = 1, length = questions.length;
		HashMap<String, Integer> questionmap = new HashMap<String, Integer>();
		for (int i = 0 ; i < length ; i++) {
			if (!questionmap.containsKey(questions[i])) {
				questionmap.put(questions[i], 1);
				questionsnum *= 2;
			}
		}
		return questionsnum;
	}
}

Challengeの時に気づいたのですが、HashSetなるものがあったんですね。

さらに、addAllとArrays.asListで配列をコレクションに変換すれば

もっと短くできることが判明。

import java.util.HashSet;

public class TheQuestionsAndAnswersDivTwo {
	public int find(String[] questions) {
		HashSet<String> questionSet = new HashSet<String>();
		questionSet.addAll(java.util.Arrays.asList(questions));
		return (int) Math.pow(2, questionSet.size());
	}
}

2010-01-21SRM459(DIV2)

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

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