Hatena::Grouptopcoder

TopCoder戦記

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

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