Hatena::Grouptopcoder

TopCoder戦記

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

2009-10-16SRM423 DIV2

SRM423 DIV2 Level Two(600pt.)

| 00:43

http://www.topcoder.com/stat?c=problem_statement&pm=9976&rd=13514

『無限の広さを持つボード上にチェッカーが並べられている。チェッカーのうち1個・2個・3個……を同一セル上に集約するとき、最小の手数(チェッカーを動かす回数)を求めよ。』

自力ではアルゴリズムを導出できず時間切れ。「手数を少なくするためには集約するセルとして(x[i],y[j])を選ぶ必要がある」という点に気づければ得に工夫は無いコードとなります。

// Time out.
import java.util.Arrays;

public class TheTower {
	public int[] count(int[] x, int[] y) {
		final int points = x.length;
		final int[] result = new int[points];
		Arrays.fill(result, Integer.MAX_VALUE);
		for (int px : x) {
			for (int py : y) {
				// (px, py)にチェッカーを集約した場合を考える
				final int[] distances = new int[points];
				for (int i = 0; i < points; ++i) {
					distances[i] = Math.abs(px - x[i]) + Math.abs(py - y[i]);
				}
				Arrays.sort(distances);
				int moves = 0;
				for (int i = 0; i < points; ++i) {
					moves += distances[i];
					result[i] = Math.min(result[i], moves);
				}
			}
		}
		return result;
	}
}