Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2010-03-21

SRM464 Div2 Medium(500pt.)

| 23:10

http://www.topcoder.com/stat?c=problem_statement&pm=10724&rd=14149

TLE解消せず。

import java.util.HashSet;
import java.util.Set;

public class ColorfulStrings {
	public String getKth(int n, int k) {
		if (n == 1) {
			return k > 10 ? "" : Integer.toString(k - 1);
		}
		if (n > 8 || k > f(8) / f(8 - n)) return "";

		int found = 0, end = endOf(n), i;
		for (i = beginOf(n); found < k && i < end; ++i) {
			if (isColorful(i)) ++found;
		}
		final String result = Integer.toString(i - 1);
		return result.length() == n ? result : "";
	}

	private int endOf(int n) {
		int result = 1;
		for (int i = 0; i < n; ++i) {
			result = result * 10;
		}
		return result + 1;
	}

	private int f(int i) {
		return i > 1 ? i * f(i - 1) : 1;
	}

	private int beginOf(int n) {
		if (n == 1) return 0;

		int result = 0;
		for (int i = 0; i < n; ++i) {
			result = result * 10 + (i + 1);
		}
		return result;
	}

	private boolean isColorful(int num) {
		final String asStr = Integer.toString(num);
		if (asStr.contains("0") || asStr.contains("1")) {
			return false;
		}
		final Set<Integer> products = new HashSet<Integer>();

		for (int start = 0; start < asStr.length(); ++start) {
			for (int end = start + 1; end <= asStr.length(); ++end) {
				if (!products.add(productOf(asStr, start, end))) return false;
			}
		}
		return true;
	}

	private Integer productOf(String string, int start, int end) {
		int answer = 1;
		for (int i = start; i < end; ++i) {
			answer *= string.charAt(i) - '0';//Character.digit(string.charAt(i), 10);
		}
		return Integer.valueOf(answer);
	}
}

2010-03-13

SRM463 DIV1 Medium(500pt.)

| 17:34

http://www.topcoder.com/stat?c=problem_statement&pm=10760&rd=14148

本番ではすべての組み合わせを行うコードを書いてみたものの、5番目のサンプルすら通らず。TopSubmissionを見たところ非常に単純なコードで驚きました。「加算した結果を再度加算することはない」「N個の数値を加算するとき、i番めとN-i-1番めを加算する」というシンプルな規則に気づけなければこのコードには至れないでしょう。

import java.util.Arrays;

public class Nisoku {
	public double theMax(double[] cards) {
		Arrays.sort(cards);
		double answer = 0.0d;
		for (int border = 0; border <= cards.length; border += 2) {
			double total = 1.0d;

			for (int i = 0; i < border; i += 2) {
				total *= cards[i] + cards[border - i - 1];
			}
			for (int i = border; i < cards.length; ++i) {
				total *= cards[i];
			}

			answer = Math.max(answer, total);
		}
		return answer;
	}
}

2010-02-18SRM462 Div2

SRM462 Div2 Level Two(500pt.)

| 18:00

http://www.topcoder.com/stat?c=problem_statement&pm=10589&rd=14147

『1と0によって構成された文字列が与えられる。この文字列が与えられた数値を表すように、何進数表記であるかを求めよ。』

解答の範囲が(0,100]であることと文字列のパース処理(parseメソッド)が基数に対する増加関数であることに目をつけて、基数について2分探索を行いました。残念ながら本番では基数がstrictly positive=ゼロが許されないことを見落としており、数多くのテストを行ったものの解くことができませんでした。確かに0進数があるはずもなく、よく考えれば気づけたはずの失敗です。

public class AgeEncoding {
	public double getRadix(int age, String candlesLine) {
		if (age == 1 && parse(candlesLine, 2) == 1) {
			return -2;
		}
		if (candlesLine.indexOf('1') < 0) {
			return -1;
		}

		double max = 100;
		double min = 0;
		for (int i = 0; i < 300; ++i) {
			final double value = parse(candlesLine, (max + min) / 2);
			if (Double.compare(value, age) < 0) {
				min = (max + min) / 2;
			} else {
				max = (max + min) / 2;
			}
		}

		final double finish = parse(candlesLine, max);
		if (Math.abs(finish - age) < 0.0001 && min > 0) {	// min must be strictly positive
			return min;
		} else {
			return -1;
		}
	}

	private double parse(String candlesLine, double d) {
		double result = 0;
		double dd = 1;

		for (int i = candlesLine.length() - 1; i >= 0; --i) {
			if (candlesLine.charAt(i) == '1') {
				result += dd;
			}
			dd *= d;
		}
		return result;
	}
}

2010-02-06

SRM410 DIV1 Level Three(1000pt.)

| 11:14

http://www.topcoder.com/stat?c=problem_statement&pm=9733&rd=12182

AWTを使い、低速だが簡潔なコードを実装。x,yがそれぞれ10^9に到達することから考えても、単純な数えあげでは実装できないようです。ビット演算を使うべき?

import java.awt.Polygon;
import java.awt.Rectangle;

public class WifiPlanet {
	public long routersNeeded(int[] x, int[] y, int denom) {
		final Polygon p = new Polygon(x, y, x.length);
		final Rectangle r = p.getBounds();
		long count = 0L;

		for (int py = r.y / denom * denom; py < r.y + r.height; py += denom) {
			for (int px = r.x / denom * denom; px < r.x + r.width; px += denom) {
				if (p.contains(px, py)) {
					++count;
				}
			}
		}
		return count;
	}
}

2010-01-28

SRM411 DIV1 Level Three(1000pt.)

| 21:48

http://www.topcoder.com/stat?c=problem_statement&pm=7620&rd=12183

時間切れで解答失敗。TopSubmissionも存在しないため、自力で到達したコードを残しておきます。

import java.util.Arrays;

public class MinimumTours {
	private int[][] map;
	private boolean[][] searched;
	private int width;
	private int height;
	private int islandId;

	public int getMinimumTours(String[] islandMap) {
		height = islandMap.length;
		width = islandMap[0].length();
		initMap(islandMap);

		final int ISLAND_MAX = islandId;
		final boolean connectable[][] = new boolean[ISLAND_MAX][ISLAND_MAX];
		for (int i = 0; i < ISLAND_MAX; ++i) {
			for (int j = i; j < ISLAND_MAX; ++j) {
				connectable[i][j] = connectable[j][i] = i == j || find(i, j);
			}
		}

		for (int j = 0; j < ISLAND_MAX; ++j) {
			System.out.println(Arrays.toString(connectable[j]));
		}

		int tours = 0;
		while(islandId > 0) {
			int minId = 0;
			int min = Integer.MAX_VALUE;
			for (int i = 0; i < ISLAND_MAX; ++i) {
				int count = 0;
				for (int j = 0; j < ISLAND_MAX; ++j) {
					if (connectable[i][j]) ++count;	// [i][i]は常に真
				}
				if (count > 0 && count < min) {
					minId = i;
					min = count;
				}
			}
			islandId -= clear(connectable, minId);
			++tours;
		}
		return tours;
	}

	// この実装が未解決
	private int clear(boolean[][] connectable, int minId) {
		int count = 1;
		for (int i = 0; i < connectable[minId].length; ++i) {
			if (connectable[minId][i] && i != minId) {
				connectable[minId][i] = connectable[i][minId] = false;
				count += clear(connectable, i);
			}
		}
		return count;
	}

	private boolean find(int fromId, int toId) {
		searched = new boolean[width][height];
		for (int x = 0; x < width; ++x) {
			for (int y = 0; y < height; ++y) {
				if (map[x][y] == fromId) {
					return findFrom(x, y, fromId, toId);
				}
			}
		}
		return false;
	}

	private boolean findFrom(int x, int y, int fromId, int toId) {
		if (searched[x][y]) return false;
		searched[x][y] = true;

		if (map[x][y] == toId) {
			return true;
		} else if (map[x][y] == -1 || map[x][y] == fromId) {
			boolean result = false;
			if (x > 0) result = findFrom(x - 1, y, fromId, toId);
			if (!result && y > 0) result = findFrom(x, y - 1, fromId, toId);
			if (!result && x < width - 1) result = findFrom(x + 1, y, fromId, toId);
			if (!result && y < height - 1) result = findFrom(x, y + 1, fromId, toId);
			return result;
		} else {
			return false;
		}
	}

	private void initMap(String[] islandMap) {
		map = new int[width][height];
		for (int y = 0; y < height; ++y) {
			for (int x = 0; x < width; ++x) {
				map[x][y] = islandMap[y].charAt(x) == 'x' ? -2 : -1;
			}
		}
		for (int y = 0; y < height; ++y) {
			for (int x = 0; x < width; ++x) {
				if (map[x][y] == -2) fill(x, y, islandId++);
			}
		}
		for (int j = 0; j < map.length; ++j) {
			System.out.println(Arrays.toString(map[j]));
		}
	}

	private void fill(int x, int y, int id) {
		if (map[x][y] == -2) {
			map[x][y] = id;
			if (x > 0) fill(x - 1, y, id);
			if (y > 0) fill(x, y - 1, id);
			if (x < width - 1) fill(x + 1, y, id);
			if (y < height - 1) fill (x, y + 1, id);
		}
	}
}