Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-10SRM346 (Practice)

SRM 346 Meteorites

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

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

  • 各隕石ごとに他の隕石で覆われている部分をラジアンの区間で持つ。
    • 角度の計算はatan2を使うと場合分けしなくて済み楽。
  • 隕石が他の隕石に完全に含まれている場合に注意する
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Meteorites {

	class Seg implements Comparable<Seg> {
		double from;
		double to;
		Seg(double f, double t) {
			from = f;
			to = t;
		}
		public int compareTo(Seg arg0) {
			int c = Double.compare(from, arg0.from);
			if (c == 0) {
				return Double.compare(to, arg0.to);
			}
			return c;
		}
		public String toString() {
			return (from + "-" + to);
		}
	}
	
	public double perimeter(int[] x, int[] y, int[] r) {
		int len = x.length;
		double ret = 0.0d;
		for (int i = 0 ; i < len ; i++) {
			List<Seg> list = new ArrayList<Seg>();
			boolean insideof = false;
			for (int j = 0 ; j < len ; j++) {
				if (i == j) {
					continue;
				}
				long dx = x[i] - x[j];
				long dy = y[i] - y[j];
				long d2 = dx * dx + dy * dy;
				long dr1 = r[i] + r[j];
				long dr2 = r[i] - r[j];
				long lr1 = r[i];
				long lr2 = r[j];
				if (d2 <= dr2 * dr2 && r[i] < r[j]) {
					insideof = true;
					break;
				} else if (dr2 * dr2 < d2 && d2 < dr1 * dr1) {
					double radA = Math.atan2((y[j] - y[i]), (x[j] - x[i])) + Math.PI * 2;
					if (radA >= Math.PI * 2) {
						radA -= Math.PI * 2;
					}
					double radX = Math.acos((lr1 * lr1 + d2 - lr2 * lr2 * 1.0d) / (2.0d * lr1 * Math.sqrt(d2)));

					double from = radA - radX;
					double to = radA + radX;
					if (from < 0) {
						from += 2 * Math.PI;
					}
					if (to < 0) {
						to += 2 * Math.PI;
					}
					if (from > Math.PI * 2) {
						from -= 2 * Math.PI;
					}
					if (to > Math.PI * 2) {
						to -= 2 * Math.PI;
					}
					
					if (from < to) {
						list.add(new Seg(from, to));
					} else {
						list.add(new Seg(from, Math.PI * 2));
						list.add(new Seg(0, to));
					}
				}
			}
			
			if (!insideof) {
				double now = 0.0d;
				double earn = 0.0d;
				int l = list.size();
				Collections.sort(list);
				
				for (int j = 0 ; j < l ; j++) {
					Seg s = list.get(j);
					if (now < s.from) {
						earn += (s.from - now);
						now = s.to;
					} else if (now <= s.to) {
						now = s.to;
					}
				}
				earn += (2 * Math.PI - now);
				ret += earn * r[i];
			}
		}
		return ret;
	}
}

2012-04-04SRM349 (Practice)

SRM 348 NormalizingTrees

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

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


問題結果ポイントその他
250RadarFinderAccepted225.03幾何、場合分け
500DiceGamesAccepted481.35数え上げ
1000LastMarbleWA0.00ゲーム

SRM 349 LastMarble

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

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

  • ゲーム木実装するだけ?
    • 書いてみた。最後以外サンプル通った。
    • 最後以外、removed = 0 だった
  • あとは remove >= 1 の場合を考慮するだけ。
    • 100C50ぐらいの値が必要になるような・・・
    • 工夫することで組み合わせ計算を省略できた
  • サンプル合った。提出
  • WA。何故・・・
    • ランダムに取り除く時、その結果は観測できないらしい
    • そもそも考え方が間違っていた・・・

通らないコード

import java.util.Arrays;

public class LastMarble {

	double[][] memo;
	
	
	public double dfs(int r, int b) {
		if (r == 0) {
			return 1.0d;
		}
		if (memo[r][b] >= 0.0d) {
			return 0.0d;
		}
		
		double minprob = 1.0d;
		
		int total = r + b;
		if (total >= 1) {
			double pr = (double) r / total;
			double pb = (double) b / total;
			double p = 0.0d;
			if (pr > 0.0d) {
				p += pr * dfs(r-1, b);
			}
			if (pb > 0.0d) {
				p += pb * dfs(r, b-1);
			}
			minprob = Math.min(minprob, p);
		}
		if (total >= 2) {
			double prr = ((double) r / total) * ((double) (r-1) / (total-1));
			double prb = ((double) r / total) * ((double) b / (total-1)) * 2;
			double pbb = ((double) b / total) * ((double) (b-1) / (total-1));
			double p = 0.0d;
			if (prr > 0.0d) {
				p += prr * dfs(r-2, b);
			}
			if (prb > 0.0d) {
				p += prb * dfs(r-1, b-1);
			}
			if (pbb > 0.0d) {
				p += pbb * dfs(r, b-2);
			}
			minprob = Math.min(minprob, p);
		}
		if (total >= 3) {
			double p = 0.0d;
			for (int tr = 0 ; tr <= 3 ; tr++) {
				for (int tb = 0 ; tb <= 3 ; tb++) {
					if (tr + tb != 3) {
						continue;
					}
					if (tr > r || tb > b) {
						continue;
					}
					double prrrbbb = 1.0d;
					for (int nr = 0 ; nr < tr ; nr++) {
						prrrbbb *= (double)(r - nr) / (total - nr);
					}
					for (int nb = 0 ; nb < tb ; nb++) {
						prrrbbb *= (double)(b - nb) / (total - tr - nb);
					}
					if (tr == 1 || tb == 1) {
						prrrbbb *= 3;
					}
					if (prrrbbb > 0.0d) {
						p += prrrbbb * dfs(r - tr, b - tb);
					}
				}
			}
			minprob = Math.min(minprob, p);
		}
		
		memo[r][b] = 1.0d - minprob;
		return memo[r][b];
	}
	
	
	public double winningChance(int red, int blue, int removed) {
		memo = new double[150][150];
		for (int i = 0 ; i < 150 ; i++) {
			Arrays.fill(memo[i], -1.0d);
		}
		
		double p = 0.0d;
		if (removed == 0) {
			return dfs(red, blue);
		}
		
		int total = red + blue;
		for (int tr = 0 ; tr <= 3 ; tr++) {
			for (int tb = 0 ; tb <= 3 ; tb++) {
				if (tr + tb != removed) {
					continue;
				}
				if (tr > red || tb > blue) {
					continue;
				}
				double prrrbbb = 1.0d;
				
				int dop = Math.min(tr, tb);
				for (int nr = 0 ; nr < tr ; nr++) {
					if (nr < dop) {
						prrrbbb *= (double)(red - nr) / (removed - nr);
					} else {
						prrrbbb *= (double)(red - nr) / (total - nr);
					}
				}
				for (int nb = 0 ; nb < tb ; nb++) {
					if (tr + nb < dop) {
						prrrbbb *= (double)(blue - nb) / (removed - tr - nb);
					} else {
						prrrbbb *= (double)(blue - nb) / (total - tr - nb);
					}
				}
				if (prrrbbb > 0.0d) {
					memo = new double[150][150];
					for (int i = 0 ; i < 150 ; i++) {
						Arrays.fill(memo[i], -1.0d);
					}
					p += prrrbbb * dfs(red - tr, blue - tb);
				}
			}
		}
		return p;
	}
}

2012-04-03SRM350, SRM351, SRM352 (Practice)

SRM 350 PlaneDivision

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

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

  • 幾何。典型問題っぽい?
  • あとでやろう。

SRM 351 NewMagicSquare

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

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

  • 見てない

後で

  • やってみた
    • これただの最大流だ
  • 辞書順最小に数字を当てはめながら最大流するだけ。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class NewMagicSquare {
	public class Edge {
		int to;
		int cap;
		int rev;
		public Edge(int _to, int _cap, int _rev) {
			to = _to;
			cap = _cap;
			rev = _rev;
		}
	}
	public Map<Integer, List<Edge>> graph = new HashMap<Integer, List<Edge>>();
	public boolean[] used;
	public void init(int size) {
		for (int i = 0 ; i < size ; i++) {
			graph.put(i, new ArrayList<Edge>());
		}
		used = new boolean[size];
	}
	public void edge(int from, int to, int cap) {
		graph.get(from).add(new Edge(to, cap, graph.get(to).size()));
		graph.get(to).add(new Edge(from, 0, graph.get(from).size() - 1));
	}
	public int dfs(int v, int t, int f) {
		if (v == t) return f;
		used[v] = true;
		for (int i = 0 ; i < graph.get(v).size() ; i++) {
			Edge e = graph.get(v).get(i);
			if (!used[e.to] && e.cap > 0) {
				int d = dfs(e.to, t, Math.min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					graph.get(e.to).get(e.rev).cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	public int max_flow(int s, int t) {
		int flow = 0;
		while (true) {
			used = new boolean[graph.size()];
			int f = dfs(s, t, Integer.MAX_VALUE);
			if (f == 0) {
				break;
			}
			flow += f;
		}
		return flow;
	}
	
	public boolean isok(int[][] tbl, boolean[] used) {
		init(52);
		for (int n = 0 ; n < 25 ; n++) {
			edge(50, n, 1);
			edge(25+n, 51, 1);
		}
		
		for (int r = 0 ; r < 5 ; r++) {
			for (int c = 0 ; c < 4 ; c++) {
				if (tbl[r][c] >= 0 && tbl[r][c+1] >= 0) {
					if (tbl[r][c] > tbl[r][c+1]) {
						return false;
					}
				}
			}
		}
		
		for (int r = 0 ; r < 5 ; r++) {
			for (int c = 0 ; c < 5 ; c++) {
				int pos = r * 5 + c;
				if (tbl[r][c] == -1) {
				} else {
					edge(tbl[r][c], 25+pos, 1);
				}
			}
		}
		
		for (int n = 0 ; n < 25 ; n++) {
			if (used[n]) {
				continue;
			}
			for (int r = 0 ; r < 5 ; r++) {
				for (int c = 0 ; c < 5 ; c++) {
					boolean isok = true;
					for (int b = 0 ; b < c ; b++) {
						if (tbl[r][b] >= 0 && tbl[r][b] > n) {
							isok = false;
							break;
						}
					}
					for (int b = c+1 ; b < 5 ; b++) {
						if (tbl[r][b] >= 0 && tbl[r][b] < n) {
							isok = false;
							break;
						}
					}
					if (isok) {
						edge(n, 25+r*5+c, 1);
					}
				}
			}
		}
		
		
		return (max_flow(50, 51) == 25);
	}
	
	public String[] completeTheSquare(String[] square) {
		int[][] tbl = new int[5][5];
		
		boolean[] used = new boolean[25];
		for (int i = 0 ; i < 5 ; i++) {
			String[] d = square[i].split(" ");
			for (int j = 0 ; j < 5 ; j++) {
				if ("??".equals(d[j])) {
					tbl[i][j] = -1;
				} else {
					tbl[i][j] = Integer.valueOf(d[j]) - 1;
					used[tbl[i][j]] = true;
				}
			}
		}
		
		for (int r = 0 ; r < 5 ; r++) {
			for (int c = 0 ; c < 5 ; c++) {
				if (tbl[r][c] == -1) {
					boolean isok = false;
					for (int n = 0 ; n < 25 ; n++) {
						if (used[n]) {
							continue;
						}
						tbl[r][c] = n;
						used[n] = true;
						if (isok(tbl, used)) {
							isok = true;
							break;
						}
						used[n] = false;
					}
					if (!isok) {
						return new String[]{};
					}
				}
			}
		}
		
		String[] ret = new String[5];
		for (int r = 0 ; r < 5 ; r++) {
			ret[r] = to2str(tbl[r][0]+1);
			for (int c = 1 ; c < 5 ; c++) {
				ret[r] += " " + to2str(tbl[r][c]+1);
			}
		}
		return ret;
	}

	public String to2str(int i) {
		if (i >= 10) {
			return String.valueOf(i);
		} else {
			return "0" + String.valueOf(i);
		}
	}
}

2012-04-02SRM353, SRM354 (Practice)

SRM 354 RooksPlacement

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

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

  • シンプルなDPのはずだがなかなか答えが合わず。
    • 考えてる状態数が足りないことに時間切れ直前になって気づいた
  • 通した。
    • 考察が足りなかった
public class RooksPlacement {
	long MOD = 1000001;
	int n, m, k;
	int K;
	long[][][] memo;
	long[][] ncr;
	
	public long ncr(int a, int b) {
		if (b > a) {
			return 0;
		}
		if (a <= 0) {
			return 0;
		}
		return ncr[a][b];
	}
	
	public long dfs(int now, int cv1, int cv2) {
		int left = k - cv1 - cv2; 
		if (now == n) {
			if (left == 0) {
				return 1;
			}
			return 0;
		} else if (now > n) {
			return 0;
		}
		if (memo[now][cv1][cv2] >= 0) {
			return memo[now][cv1][cv2];
		}
		if (left <= -1) {
			return 0;
		}

		long ret = 0;
		int free0 = m - cv1;
		
		// place two
		{
			long f02 = ncr(free0, 2);
			if (f02 >= 1) {
				ret += dfs(now+1, cv1+2, cv2) * f02;
				ret %= MOD;
			}
		}

		// place one
		{
			if (free0 >= 1) {
				ret += dfs(now+1, cv1+1, cv2) * free0;
				ret %= MOD;
			}
			
			long r2 = ncr(n - now - 1, 1);
			if (r2 >= 1 && free0 >= 1) {
				ret += dfs(now+2, cv1+1, cv2+1) * r2 * free0;
				ret %= MOD;
			}
		}
		
		// dont place
		ret += dfs(now+1, cv1, cv2);
		
		memo[now][cv1][cv2] = ret;
		return ret;
	}
	
	public int countPlacements(int N, int M, int K) {
		n = N;
		m = M;
		k = K;
		memo = new long[101][101][101];
		for (int i = 0 ; i < 101 ; i++) {
			for (int j = 0 ; j < 101 ; j++) {
				for (int k = 0 ; k < 101 ; k++) {
					memo[i][j][k] = -1;
				}
			}
		}
		ncr = new long[201][201];
		for (int i = 0 ; i < 201 ; i++) {
			ncr[i][0] = 1;
			ncr[i][i] = 1;
			for (int j = 1 ; j < i ; j++) {
				ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j]) % MOD;
			}
		}
		
		return (int)(dfs(0, 0, 0) % MOD);
	}
}