Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

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

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

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


SRM494 第一問(250pt) Painting

|  SRM494 第一問(250pt) Painting - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM494 第一問(250pt) Painting - hama_DU@TopCoderへの道

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

大きいブラシから塗れるかどうか試していけばおk


public class Painting {
	public int largestBrush(String[] picture) {
		int y = picture.length;
		int x = picture[0].length();
		int[][] pic = new int[y][x];
		int blacks = 0;
		for (int i = 0; i < y; i++) {
			for (int j = 0; j < x; j++) {
				pic[i][j] = (picture[i].charAt(j) == 'B') ? 0 : 1;
				blacks += 1 - pic[i][j];
			}
		}
		int now = Math.min(x, y);
		int min = 1;

		System.err.println(x + "," + y);

		for (; now >= min ; now--) {
			boolean isok = true;
			boolean[][] painted = new boolean[y][x];
			int nums = 0;
			for (int i = 0; i <= y - now; i++) {
				for (int j = 0; j <= x - now; j++) {
					if (pic[i][j] == 1) {
						continue;
					}
					int n = 0;
					for (int ay = i; ay < i + now; ay++) {
						for (int ax = j; ax < j + now; ax++) {
							n += pic[ay][ax];
						}
					}
					if (n == 0) {
						for (int ay = i; ay < i + now; ay++) {
							for (int ax = j; ax < j + now; ax++) {
								painted[ay][ax] = true;
								nums++;
							}
						}
					}
				}
			}
			isok = true;
			search2:
			for (int i = 0; i < y ; i++) {
				for (int j = 0; j < x ; j++) {
					if (!painted[i][j] && pic[i][j] == 0) {
						isok = false;
						break search2;
					}
				}
			}
			if (isok) {
				return now;
			}
		}
		return 1;
	}
}

SRM494 第二問(500pt) AlternatingLane

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

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

各木の間のBeauty期待値を計算していけばいい、ということに気づきさえすれば簡単。

あとは 100,000 * 100,000 でintの範囲を超えてしまうため、longで計算することに気をつける。


public class AlternatingLane {
	public long sumexternal(int f, int c, int d) {
		long cthigh = d - c + 1;
		long sumhigh = (d + c) * cthigh / 2;
		long ct = 0;
		ct += sumhigh;
		ct = Math.abs(sumhigh - f * cthigh);
		return ct;
	}

	public long suminternal(int f, int c, int d) {
		long ct = 0;
		ct += (long)(f - c) * (long)(f - c + 1) / 2;
		ct += (long)(d - f) * (long)(d - f + 1) / 2;
		return ct;
	}

	public double expectedBeauty(int[] low, int[] high) {
		int len = low.length;
		if (len == 1) {
			return 0;
		}

		double res = 0.0d;
		for (int i = 0 ; i < len - 1 ; i++) {
			long ct = 0;
			for (int f = low[i] ; f <= Math.min(low[i+1] - 1, high[i]) ; f++) {
				ct += sumexternal(f, low[i+1], high[i+1]);
			}
			for (int f = Math.max(low[i+1], low[i]) ; f <= Math.min(high[i+1], high[i]) ; f++) {
				ct += suminternal(f, low[i+1], high[i+1]);
			}
			for (int f = Math.max(high[i+1] + 1, low[i]) ; f <= high[i] ; f++) {
				ct += sumexternal(f, low[i+1], high[i+1]);
			}
			res += (double)ct / (double)((long)(high[i+1] - low[i+1] + 1) * (long)(high[i] - low[i] + 1));
			System.out.println(res + "/");
		}

		return res;
	}
}