Hatena::Grouptopcoder

gnarl,TopCoder

 | 

2010-04-23

Topcoder Member SRM 468 Div2 1000: Gifts

22:53

本番じゃ時間なくて解けなかったのをやってみた(未完)。


迷路上にKing,Queen,Gift(これは複数)が配置されている。KingはGiftを拾いながらQueenに会いに行く(制限時間T)。なるべく多くのGiftを渡したい。

1マス動くのに(1+拾ったGiftの数)秒かかる。

最初のステップで各ノード(king,queen,gifts)間の最短距離を計算しとく。次のステップではgiftの組み合わせを試しながら渡せる最大数を求める…… と(ご想像の通り)テストケースによっては組み合わせ爆発が発生していくら待っても終わらない!

どうやらDPに落とし込むのが正解のようだが、どうやってDPを適用すればいいのか理解できず。訓練が必要。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Gifts {
	static class P {
		public P(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public final int x;
		public final int y;

		@Override
		public boolean equals(Object obj) {
			if (obj instanceof P)
				return equals((P) obj);
			return false;
		}

		public boolean equals(P that) {
			return this.x == that.x && this.y == that.y;
		}

		@Override
		public int hashCode() {
			return Integer.valueOf(x).hashCode()
					^ Integer.valueOf(y).hashCode();
		}

		@Override
		public String toString() {
			return "(" + x + "," + y + ")";
		}
	}

	public int maxGifts(String[] city, int T) {
		System.out.println("========================");
		System.out.println("T=" + T);
		for (String row : city)
			System.out.println(row);

		final int H = city.length;
		final int W = city[0].length();

		// 0: king 1: queen 2+n: gift #n
		final List<P> pos = new ArrayList<P>();
		// king(placeholder)
		pos.add(null);
		// queen(placeholder)
		pos.add(null);

		// find the positions of king,queen,gifts
		for (int r = 0; r < H; r++) {
			for (int c = 0; c < W; c++) {
				final char ch = city[r].charAt(c);
				switch (ch) {
				case 'K':
					pos.set(0, new P(c, r));
					break;
				case 'Q':
					pos.set(1, new P(c, r));
					break;
				case 'G':
					pos.add(new P(c, r));
					break;
				}
			}
		}

		System.out.println(pos);

		// find the minimum distances
		final int[][] dists = new int[pos.size()][];
		for (int i = 0; i < pos.size(); i++) {
			dists[i] = new int[pos.size()];
			for (int j = 0; j < pos.size(); j++)
				dists[i][j] = minDist(city, pos.get(i), pos.get(j));
		}

		for (int[] row : dists) {
			for (int col : row)
				System.out.print(col + "\t");
			System.out.println();
		}

		final boolean[] picked = new boolean[pos.size()];
		// these are not gift
		picked[0] = true; // king
		picked[1] = true; // queen

		return maxGifts(0, dists, picked, 0, 0, T);
	}

	private int maxGifts(int pos, int[][] dists, boolean[] picked, int weight,
			int t, int maxT) {
		if (weight == 0)
			System.out.println("search:");
		System.out.println("  t=" + t);
		final boolean unreachableToQueen = t + dists[pos][1] * (weight + 1) > maxT;
		if (unreachableToQueen) {
			System.out.println("  cut");
			return 0;
		}
		int max = weight;
		for (int i = 0; i < picked.length; i++) {
			if (!picked[i] && dists[pos][i] != -1) {
				System.out.println("  pick " + i);
				picked[i] = true;
				max = Math.max(max, maxGifts(i, dists, picked, weight + 1, t
						+ dists[pos][i] * (1 + weight), maxT));
				picked[i] = false;
			}
		}
		return max;
	}

	private int minDist(String[] city, P p0, P p1) {
		if (p0.equals(p1))
			return 0;
		final LinkedList<P> sp = new LinkedList<P>();
		sp.addFirst(p0);

		int[][] dists = new int[city.length][];
		for (int i = 0; i < dists.length; i++) {
			dists[i] = new int[city[0].length()];
			Arrays.fill(dists[i], Integer.MAX_VALUE);
		}
		dists[p0.y][p0.x] = 0;

		final int[][] dirs = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 },
				{ 0, 1 } };

		while (!sp.isEmpty()) {
			final P p = sp.removeLast();
			for (int[] dir : dirs) {
				final int nextDist = dists[p.y][p.x] + 1;
				final int x = p.x + dir[0];
				final int y = p.y + dir[1];
				if (p1.x == x && p1.y == y)
					return nextDist;

				final char c = tileAt(city, y, x);
				if (c != '#') {
					if (dists[y][x] > nextDist) {
						dists[y][x] = nextDist;
						sp.addFirst(new P(x, y));
					}
				}
			}
		}
		return -1;
	}

	private char tileAt(String[] city, int r, int c) {
		if (r < 0 || city.length <= r)
			return '#';
		if (c < 0 || city[0].length() <= c)
			return '#';
		return city[r].charAt(c);
	}
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/gnarl/20100423
 |