Hatena::Grouptopcoder

TopCoder戦記

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

2009-08-26SRM447 DIV2

結果は231.66ptで、1017名中374位。Level Twoはアルゴリズムを完全に理解できたにも関わらず、原因不明の挙動によって例題すら解くことができませんでした。

SRM447 DIV2 Level One(250pt.)

| 12:05

複数のコンピュータに複数のタスクを分配するとき、実行可能なタスクの数を求める問題。あらかじめ要素をソートしておくことで、単純な突合せで解答することができます。「最もコストの低いタスクすらこなせないのなら、他のすべてのタスクは実行できない」という事実をもとに、組み合わせを削減する手法を採っています。

// 261.66 pt.
import java.util.Arrays;

public class ImportantTasks {
	public int maximalCost(int[] complexity, int[] computers) {
		Arrays.sort(computers);
		Arrays.sort(complexity);

		int cost = 0;
		int taskIdx = 0;
		for (int i = 0; i < computers.length && taskIdx < complexity.length; ++i) {
			if (computers[i] >= complexity[taskIdx]) {
				taskIdx++;
				cost++;
			}
		}
		return cost;
	}
}

SRM447 DIV2 Level Two(500pt.)

| 12:05

チェスの騎士(ナイト)を一定のルールにしたがって動かすとき、騎士が移動するマスの総数を計算する。アルゴリズムは理解できましたがなぜか例題すら通らず、恥ずかしながらバグがまだ見つかっていません。デバッグ情報からaccessibleNumberの算出に問題があるかと思い、何度も見直したのですが……。非常に基本的なところを間違えていそうで恐ろしいです。

位置を表すためにImmutableなクラスを作成しているのですが、同じ部屋の皆さんを見る限りなかなか珍しい手法のようです。発想としてはありふれていると思うのですが、やはりコストやコーディングのスピードを懸念する方々が多いのでしょうか。

import java.util.PriorityQueue;

public class KnightsTour {
	private static final int[] MCOL = new int[] { 2, 1, -1, -2, -2, -1, 1, 2 };
	private static final int[] MROW = new int[] { 1, 2, 2, 1, -1, -2, -2, -1 };

	public int visitedPositions(String[] board) {
		int visitedCells = 1; // including start cell
		Cell knightCell = getKnightCell(board);
		boolean[][] visited = new boolean[8][8];
		for (int r = 0; r < board.length; ++r) {
			for (int c = 0; c < board[r].length(); ++c) {
				visited[r][c] = board[r].charAt(c) != '.';
			}
		}

		while ((knightCell = getNext(visited, knightCell)) != null) {
			visitedCells++;
			visited[knightCell.row][knightCell.col] = true;
		}
		return visitedCells;
	}

	private Cell getNext(boolean[][] visited, Cell knightCell) {
		PriorityQueue<Cell> que = new PriorityQueue<Cell>(8);
		int minimumAccessibleNumber = Integer.MAX_VALUE;
		
		for (int i = 0; i < MCOL.length; ++i) {
			int r = MROW[i] + knightCell.row;
			int c = MCOL[i] + knightCell.col;
			if (c < 0 || r < 0 || 8 <= c || 8 <= r) {
				continue;
			} else if (!visited[r][c]) {
				Cell cell = new Cell(r, c);
				int aNum = calcAccessibleNumber(visited, cell);
				if (aNum < minimumAccessibleNumber) {
					minimumAccessibleNumber = aNum;
					que.clear();
				}
				que.add(cell);
			}
		}

		return que.peek();
	}

	private Cell getKnightCell(String[] board) {
		for (int r = 0; r < board.length; ++r) {
			for (int c = 0; c < board[r].length(); ++c) {
				if (board[r].charAt(c) == 'K') {
					return new Cell(r, c);
				}
			}
		}
		return null;
	}
	
	private int calcAccessibleNumber(boolean[][] visited, Cell cell) {
		int num = 0;
		for (int i = 0; i < MCOL.length; ++i) {
			int r = MROW[i] + cell.row;
			int c = MCOL[i] + cell.col;
			if (c < 0 || r < 0 || 8 <= c || 8 <= r) {
				continue;
			} else if (!visited[r][c]) {
				num++;
			}
		}
		return num;
	}

	class Cell implements Comparable<Cell> {
		final int row;
		final int col;

		Cell(int row, int col) {
			this.row = row;
			this.col = col;
		}

		public int compareTo(Cell o) {
			return (this.row - o.row) * 8 + this.col - o.col;
		}
	}
}

mimanamimana2009/12/30 20:34汚ないソースですが、getNext()を以下のように変えたらシステムテスト通りました。
private Cell getNext(boolean[][] visited, Cell knightCell) {
PriorityQueue<Cell> que = new PriorityQueue<Cell>(8);
int minimumAccessibleNumber = Integer.MAX_VALUE;

for (int i = 0; i < MCOL.length; ++i) {
int r = MROW[i] + knightCell.row;
int c = MCOL[i] + knightCell.col;
if (c < 0 || r < 0 || 8 <= c || 8 <= r) {
continue;
} else if (!visited[r][c]) {
Cell cell = new Cell(r, c);
int aNum = calcAccessibleNumber(visited, cell);
if (aNum < minimumAccessibleNumber) {
minimumAccessibleNumber = aNum;
}
}
}
for(int i=0; i<MCOL.length; ++i) {
int r = MROW[i] + knightCell.row;
int c = MCOL[i] + knightCell.col;
if (c < 0 || r < 0 || 8 <= c || 8 <= r) {
continue;
} else if (!visited[r][c]) {
Cell cell = new Cell(r, c);
int aNum = calcAccessibleNumber(visited, cell);
if(aNum == minimumAccessibleNumber) {
que.add(cell);
}
}
}

return que.peek();
}

ellereller2010/01/03 08:56ご指摘感謝です。
getNextを修正して通ったということは、騎士を動かすアルゴリズムに問題があったのですね。4ヶ月近く経っていますし、再度解き直してみます。

ellereller2010/01/03 09:48AccessibleNumberが最小でないセルもジャンプ先対象としてキューにaddしてしまっているのが不具合の原因でした。
びっくりするほどのイージーミスですね。解消してよかったです。