Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-04SRM349 (Practice)

問題結果ポイントその他
250LostParenthesesAccepted208.64DP
500RailwayTicketsOpened0.00最小費用流
1000NormalizingTreesUnopened0.00見てない

SRM 348 LostParentheses

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

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

  • Greedyなアルゴリズムなんて思いつかないので、区間DPをする
import java.util.Arrays;

public class LostParentheses {
	int INF = 1000000;
	int[] nums, ops;
	int[][] memo;
	
	public int dfs(int from, int to) {
		if (from == to) {
			return nums[from];
		}
		if (memo[from][to] != INF) {
			return memo[from][to];
		}
		
		int ret = INF;
		for (int j = from ; j < to ; j++) {
			int a = dfs(from, j);
			int b = dfs(j+1, to);
			if (ops[j+1] == 1) {
				ret = Math.min(ret, a + b);
			} else if (ops[j+1] == -1) {
				ret = Math.min(ret, a - b);
			}
		}
		memo[from][to] = ret;
		return ret;
	}
	
	
	public int minResult(String e) {
		String[] numstrs = e.split("[+-]");
		nums = new int[numstrs.length];
		for (int i = 0 ; i < numstrs.length ; i++) {
			nums[i] = Integer.valueOf(numstrs[i]);
		}
		
		String[] opstrs = e.split("[0-9]+");
		ops = new int[opstrs.length];
		for (int i = 0 ; i < opstrs.length ; i++) {
			if ("+".equals(opstrs[i])) {
				ops[i] = 1;
			} else if ("-".equals(opstrs[i])) {
				ops[i] = -1;
			}
		}
		
		memo = new int[nums.length+1][nums.length+1];
		for (int i = 0 ; i < nums.length+1 ; i++) {
			Arrays.fill(memo[i], INF);
		}
		
		return dfs(0, nums.length-1);
	}
}

SRM 348 RailwayTickets

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

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

  • 蟻本第二版p220と同じ問題。
    • そのままやるとTLEするが、座標圧縮するとうまくいく。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class RailwayTickets {
	// 最小費用流のコードは省略

	class P {
		int from, to;
		P(String data) {
			String[] ft = data.split("-");
			from = Integer.valueOf(ft[0]);
			to = Integer.valueOf(ft[1]);
		}
	}

	public int minRejects(String[] travel, int seats) {
		int len = travel.length;
		List<P> p = new ArrayList<P>();
		for (int i = 0 ; i < len ; i++) {
			String[] data = travel[i].split(" ");
			int dlen = data.length;
			for (int j = 0 ; j < dlen ; j++) {
				p.add(new P(data[j]));
			}
		}
		
		int max = 0;
		int[] tcnt = new int[10001];
		for (int i = 0 ; i < p.size() ; i++) {
			P pas = p.get(i);
			tcnt[pas.from]++;
			tcnt[pas.to]++;
		}
		
		int[] idmap = new int[10001];
		int idcnt = 1;
		for (int i = 1 ; i <= 10000 ; i++) {
			if (tcnt[i] >= 1) {
				idmap[i] = idcnt;
				idcnt++;
			}
		}
		
		int start = 0;
		int goal = 10001;
		init(10002);
		
		edge(start, 1, seats, 0);
		edge(idcnt-1, goal, seats, 0);
		for (int i = 1 ; i < idcnt ; i++) {
			edge(i, i+1, INF, 0);
		}
		
		for (int i = 0 ; i < p.size() ; i++) {
			int from = idmap[p.get(i).from];
			int to = idmap[p.get(i).to];
			edge(to, from, 1, 1);
			edge(start, to, 1, 0);
			edge(from, goal, 1, 0);
		}
		
		return min_cost_flow(start, goal, seats+p.size());
	}
}

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 RadarFinder

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

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

  • 場合分け。
    • 一方の円が他方の円を完全に含む場合などに注意する
    • オーバーフローにも注意する
      • あらかじめ引数をlongに再代入しておく
public class RadarFinder {
	public int possibleLocations(int ix1, int iy1, int ir1, int ix2, int iy2, int ir2) {
		long x1 = ix1, x2 = ix2;
		long y1 = iy1, y2 = iy2;
		long r1 = ir1, r2 = ir2;
		
		if (x1 == x2 && y1 == y2) {
			if (r1 == r2) {
				return -1;
			}
			return 0;
		}
		
		long dx = Math.abs(x2 - x1);
		long dy = Math.abs(y2 - y1);
		long dist2 = dx * dx + dy * dy;
		long rr2 = (r1 + r2) * (r1 + r2);
		if (dist2 < rr2) {
			long rr1 = (r1 - r2) * (r1 - r2);
			if (dist2 < rr1) {
				return 0;
			} else if (dist2 == rr1) {
				return 1;
			}
			return 2;
		} else if (dist2 == rr2) {
			return 1;
		}
		return 0;
	}
}

SRM 349 DiceGames

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

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

  • ソートして数え上げるだけ
    • メモ化再帰を実装した
import java.util.Arrays;

public class DiceGames {
	
	int[] a;
	int len;
	
	long[][] memo;
	
	public long dfs(int i, int prev) {
		if (i == len) {
			return 1;
		}
		if (memo[i][prev] >= 0) {
			return memo[i][prev];
		}
		
		long ret = 0;
		for (int n = prev ; n <= a[i] ; n++) {
			ret += dfs(i+1, n);
		}
		memo[i][prev] = ret;
		return ret;
	}

	public long countFormations(int[] sides) {
		a = sides;
		len = sides.length;
		Arrays.sort(sides);
		
		memo = new long[50][50];
		for (int i = 0 ; i < 50 ; i++) {
			Arrays.fill(memo[i], -1);
		}
		return dfs(0, 1);
	}
}

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