Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

例外って便利ですね。

SRM458 div2 第二問(500点)

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

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

直線上に並んだボールの衝突回数の期待値を求める問題。

統計によるとこちらの方が正解率が高いのが不思議!


public class BouncingBalls {

	public double expectedBounces(int[] x, int T) {
		double exp = 0;
		int ballsNum = x.length;

		for (int i = 0 ; i < ballsNum ; i++) {
			for (int j = i + 1 ; j < ballsNum ; j++) {
				int distance = x[j] - x[i];
				if (distance <= 2 * T) {
					exp += 0.25;
				}
			}
		}
		return exp;
	}
}

はじめはボールがぶつかるケースが出たらかかった時間を引いて

再帰でゴニョゴニョしようかな、と考えましたが。

絵を描いてたらボール1つ1つとの衝突が何回おこえりえるかを

数えればいいだけのことに気づきました。(等速度なため)

SRM458 div2 第三問(950点)

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

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

ある範囲を動く整数x、y、zが与えられるとき、

x × y = z を満たす場合の数を求める問題。

問題はシンプルだが、x、y、zがそれぞれ 1 ~ 1,000,000,000 で動くため、高速化が鍵となる。


思いつく限りの高速化を施したのがこちら。

import java.util.HashSet;

public class ProductTriplet {
	public long countTriplets(int minx, int maxx, int miny, int maxy, int minz, int maxz) {
		long answers = 0;
		HashSet set = new HashSet();
		int finished = 1;

		for (int i = minz ; i <= maxz ; i++) {
			for (int j = finished ; j <= i ; j++) {
				if (set.contains(j)) {
					continue;
				}
				if (i % j == 0) {
					int k = i / j;
					if (minx <= i && miny <= k && k <= maxy ) {
						answers += (maxz - i) / j + 1;
					}
					set.add(j);
				}
			}
			finished++;
		}
		return answers;
	}
}

ある数 i について割り切れる数 x を見つけたら、

それ以降の数 (i + nx) についてもカウントしてしまおうという作戦。

だが i が大きくなってしまうと割れる数を探すのに時間がかかってしまう、

という問題があり、最後のテストケースには通らず。

別のアプローチを思いついたので後日試します。