Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-27SRM300台を練習していく part2

SRM 303 Knights

|  SRM 303 Knights - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 303 Knights - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6070

ナイトの駒の関係はグラフに帰着できる。

さらに、ナイトの動き方の制約上、駒は大きく分けて二種類に分類でき、

同じ種類の駒が関係を結ぶことはない。

(こういう特別なグラフを「2部グラフ」というらしい)

問題は、グラフのノードを取り除いて、関係(リンク)の無いグラフを作るとき、

取り除く必要のある最小のノード数を求める、というもの。

そして、この問題はどうやら「2部グラフの最大マッチング問題」というものに帰着できるらしい。

確か蟻本に載っていたような気がするので、あとで調べる。

2011-03-15div2hard 三本勝負(SRM491, 493, 497)

SRM491 div2 第三問(1000pt) BottlesOnShelf

|  SRM491 div2 第三問(1000pt) BottlesOnShelf - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM491 div2 第三問(1000pt) BottlesOnShelf - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=11008

ビットDP。頑張って自力でここまで書いた。

だがTLEする。降参


public class BottlesOnShelf {
	public long gcd(long a, long b) {
		long r = a % b;
		if (r == 0) {
			return b;
		}
		return gcd(b, r);
	}

	public long lcm(long a, long b) {
		return a * b / gcd(a, b);
	}

	public int getNumBroken(int N, int[] left, int[] right, int[] damage) {
		int M = left.length;
		int bits = (1 << M);

		int[] dp = new int[bits];
		long[] dp_min = new long[bits];
		long[] dp_max = new long[bits];
		long[] dp_lcm = new long[bits];
		dp_min[0] = 1;
		dp_max[0] = N;
		dp_lcm[0] = 1;

		for (int i = 0 ; i < bits ; i++) {
			int count = Integer.bitCount(i);
			if (count >= 1) {
				for (int j = (i - 1) & i ; j > 0 ; j = (j - 1) & i) {
					int ct = Integer.bitCount(j);
					dp[i] += dp[j] * (((count - ct) % 2 == 1) ? 1 : -1);
				}
				int max_i_1 = (i - 1) & i;
				long lcm = dp_lcm[max_i_1];
				long min = dp_min[max_i_1];
				long max = dp_max[max_i_1];
				if (min == -1) {
					dp_min[i] = -1;
					continue;
				} else {
					for (int x = 0 ; x < M ; x++) {
						int ptn = 1 << x;
						if ((max_i_1 & ptn) != 0) {
							continue;
						}
						if ((i & ptn) >= 1) {
							if (right[x] < min || max < left[x]) {
								min = -1;
								break;
							}
							lcm = lcm(lcm, damage[x]);
							if (min < left[x]) {
								min = left[x];
							}
							if (right[x] < max) {
								max = right[x];
							}
							break;
						}
					}
					dp_lcm[i] = lcm;
					dp_min[i] = min;
					dp_max[i] = max;
					if (min != -1) {
						if (min % lcm != 0) {
							min += (lcm - min % lcm);
						}
						max -= max % lcm;
						dp[i] += ((max - min) / lcm + 1) * ((count % 2 == 1) ? 1 : -1);
					}
				}
			}
		}
		return dp[(1<<M)-1];
	}
}

2011-03-13SRM494、SRM498など(DIV1)

SRM498 第二問(450pt) FoxStones

|  SRM498 第二問(450pt) FoxStones - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM498 第二問(450pt) FoxStones - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=11316

各マスを、ポイントからの距離の組み合わせによってグループ分けするだけ。


import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class FoxStones {

	public int[] Dx = {1, 0, -1, 0};
	public int[] Dy = {0, 1, 0, -1};

	public long MODULO = 1000000009;

	public int getCount(int N, int M, int[] sx, int[] sy) {
		int length = sx.length;
		ArrayList<StringBuffer> arr = new ArrayList<StringBuffer>();

		for (int x = 0 ; x < N ; x++) {
			for (int y = 0 ; y < M ; y++) {
				arr.add(new StringBuffer());
			}
		}

		for (int i = 0 ; i < length ; i++) {
			int cx = sx[i] - 1;
			int cy = sy[i] - 1;
			for (int x = 1 ; x <= 200 ; x++) {
				int nx = cx - x;
				int ny = cy - x;
				for (int d = 0 ; d < 4 ; d++) {
					for (int dd = 0 ; dd < x * 2 ; dd++) {
						nx += Dx[d];
						ny += Dy[d];
						if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
							arr.get(ny * N + nx).append(i).append("_").append(x).append(",");
						}
					}
				}
			}
		}


		Map<String, Long> ctmap = new HashMap<String, Long>(40000, 1.0f);
		for (int x = 0 ; x < N ; x++) {
			for (int y = 0 ; y < M ; y++) {
				String s = arr.get(y * N + x).toString();
				if (s.length() > 0) {
					if (ctmap.containsKey(s)) {
						ctmap.put(s, ctmap.get(s) + 1L);
					} else {
						ctmap.put(s, 1L);
					}
				}
			}
		}

		long result = 1L;
		System.out.println(ctmap.keySet().size());
		for (String key : ctmap.keySet()) {
			long l = ctmap.get(key);
			for (int n = 2 ; n <= l ; n++) {
				result = (result * n) % MODULO;
			}
		}
		return (int)result;
	}
}

簡単と思ったがそんなことはなかった。

上のコードだと時間的にはギリギリ間に合うものの、メモリを使いきってしまう。

もうちょっと効率のいい解き方があるのかも。

2010-07-19[過去問]SRM476(DIV1)

SRM476 第二問(550点)

| SRM476 第二問(550点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM476 第二問(550点) - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10806&rd=14186

方針が全く思いつきません


所感

参加してたら確実にDIV2に落ちてたな