Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-20SRM345 (Practice)

SRM 345 Pathfinding

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

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

  • 探索で解こうと思った
    • 無理だった
  • 結局場合分けした。
    • xとyは対称性を持つので片方が負の場合だけを考えれば良い
  • 解法の検討に色々迷走したので時間がかかってしまった。
public class Pathfinding {
	public int getDirections(int x, int y) {
		int dx = Math.abs(x);
		int dy = Math.abs(y);
		
		if (x >= 0 && y >= 0) {
			if (dx % 2 == 1 && dy % 2 == 1) {
				return dx + dy + 2;
			}
			return dx + dy;
		} else if (x <= 0 && y <= 0) {
			if (dx % 2 == 0 && dy % 2 == 0) {
				return dx + dy + 4;
			}
			return dx + dy + 2;
		}
		
		if (x > 0) {
			int t = x;
			x = y;
			y = t;
		}
		
		dx = Math.abs(x);
		dy = Math.abs(y);
		if (dx % 2 == 1 && dy % 2 == 0) {
			return dx + dy + 2;
		}
		return dx + dy;
	}
}

SRM 345 StoneGame

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

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

  • 手で実験してみる
    • これ、総取りできるか、全部相手に取られるかのどちらかなのでは
      • 石の総数の偶奇で決まる気がする(奇数なら総取りできる)
  • でも、石の数が1の場合はまずそちらを取った方がいい
    • 複数ある場合は当然価値が高いものを取った方がいい
    • 相手も当然価値が高いものを優先して取るはず
  • 石の数が1の山をすべて取り終えたときゲームが始まる
  • 書いたらサンプル合った。
    • 証明はできないが正しい気がするのでそのまま出した
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class StoneGame {

	public int getScore(int[] treasure, int[] stones) {
		int len = stones.length;
		List<Integer> cango = new ArrayList<Integer>();
		
		int etotal = 0;
		int etreas = 0;
		for (int i = 0 ; i < len ; i++) {
			if (stones[i] == 1) {
				cango.add(treasure[i]);
			} else {
				etotal += stones[i];
				etreas += treasure[i];
			}
		}
		Collections.sort(cango);
		Collections.reverse(cango);
		
		int canget = 0;
		int cl = cango.size();
		for (int i = 0 ; i < cl ; i += 2) {
			canget += cango.get(i);
		}
		if (cl == len) {
			return canget;
		}
		
		if (cl % 2 == 1) {
			etotal -= 1;
		}
		if (etotal % 2 == 1) {
			canget += etreas;
		}
		return canget;
	}
}

SRM 345 ByteLand

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

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

  • 貪欲で行ける気がするが、証明ができない
    • 距離を決めうちしてDPする系なのかな?
  • 後で解く

2012-04-10SRM346 (Practice)

SRM 346 CommonMultiples

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

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

  • やるだけ。
public class CommonMultiples {

	public long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a%b);
	}
	
	public long lcm(long a, long b) {
		long gcd = gcd(a, b);
		return (a / gcd) * b;
	}
	
	
	public int countCommMult(int[] a, int lower, int upper) {
		long lo = lower;
		long up = upper;
		
		long l = 1;
		for (int i = 0 ; i < a.length ;i++) {
			l = lcm(l, a[i]);
			if (l > up || l <= 0) {
				return 0;
			}
		}	
		return (int)((up / l) - ((lo - 1) / l));
	}
}

SRM 346 HeightRound

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

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

  • 貪欲法。難しい
    • editorialや他の人のコードを見ながら書いた。
    • 要復習
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class HeightRound {
	public int[] getBestRound(int[] h) {
		int len = h.length;
		Arrays.sort(h);
		int[] ret = new int[len];
		ret[0] = h[0];
		for (int d = 0 ; d <= 1000 ; d++) {
			boolean isok = true;
			List<Integer> hv = new ArrayList<Integer>();
			for (int i = 1 ; i < len ; i++) {
				hv.add(h[i]);
			}
			int q = h.length - 1;
			while (q > 0) {
				int idx = hv.size() - 1;
				int prev = (q + 1 == ret.length) ? ret[0] : ret[q+1];
				while (idx >= 0) {
					if (Math.abs(hv.get(idx) - prev) <= d) {
						break;
					}
					idx--;
				}
				if (idx < 0) {
					isok = false;
					break;
				}
				ret[q] = hv.remove(idx);
				q--;
			}
			if (Math.abs(ret[1] - ret[0]) > d) {
				continue;
			}
			if (isok) {
				return ret;
			}
		}
		return ret;
	}
}

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-05SRM347 (Practice)

SRM 347 Aircraft

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

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

  • ふつーに三分探索しようとした
    • 式が間違ってて答えが合わなかった。ひどい
  • editorial見ると二次方程式を解くのがいいらしい。なんと
public class Aircraft {
	long RR;
	public String nearMiss(int[] p1, int[] v1, int[] p2, int[] v2, int R) {
		RR = 1L * R * R;
		
		long[] np = new long[3];
		long[] dv = new long[3];
		for (int i = 0 ; i < 3 ; i++) {
			np[i] = p2[i] - p1[i];
			dv[i] = v2[i] - v1[i];
		}
		
		long A = 0, B = 0, C = 0;
		for (int i = 0 ; i < 3 ; i++) {
			A += dv[i] * dv[i];
			B += 2 * np[i] * dv[i];
			C += np[i] * np[i];
		}
		if (C <= RR) {
			return "YES";
		}
		if (A == 0 || B >= 0) {
			return "NO";
		}
		if (B * B - 4 * A * (C - R * R) >= 0) {
			return "YES";
		}
		return "NO";
	}
}

SRM 347 FlightScheduler

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

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

  • 問題文が正しく読めず、editorialを読むまで意味不明だった
  • 式変形して1回のフライトでR飛ぶときの必要燃料を求める。
    • n回に分けて飛行する場合の必要燃料を考えた時最適な回数を三分探索で探す。
public class FlightScheduler {
	int em;
	int k;
	
	public double ff(double r) {
		return 1.0d * em * (Math.pow(Math.E, (r / k)) - 1);
	}
	
	public double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel) {
		em = emptyMass;
		k = K;
		
		long tf = takeoffFuel;
		double req = Double.MAX_VALUE;
		
		long min = 1;
		long max = 1000000000L;
		for (int cur = 1 ; cur <= 10000 ; cur++) {
			long stp1 = (min * 2 + max) / 3;
			long stp2 = (min + max * 2) / 3;
			double d1 = 1.0d * distance / stp1;
			double d2 = 1.0d * distance / stp2;
			double fuel1 = tf * stp1 + ff(d1) * stp1;
			double fuel2 = tf * stp2 + ff(d2) * stp2;
			if (fuel1 > fuel2) {
				min = stp1;
			} else {
				max = stp2;
			}
		}
		
		for (long stp = min - 1000000 ; stp <= min + 1000000 ; stp++) {
			if (stp <= 0) {
				continue;
			}
			double d = 1.0d * distance / stp;
			double fuel1 = tf * stp + ff(d) * stp;
			req = Math.min(req, fuel1);
		}
		return req;
	}
}

2012-04-04SRM349 (Practice)

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

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

SRM 350 SumsOfPerfectPowers

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

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

  • 求めるべき数の中で、m >= 2 で a^m となってる数はそんなに多くない。
    • なので、全て列挙し、2つの数の組み合わせを全部試せる。
import java.util.HashSet;
import java.util.Set;

public class SumsOfPerfectPowers {
	int MAX = 8000000;
	
	public int howMany(int lowerBound, int upperBound) {
		boolean[] done = new boolean[MAX];
		Set<Integer> l = new HashSet<Integer>();
		
		for (int a = 0 ; a <= 10000 ; a++) {
			long aa = a;
			for (int m = 2 ; m <= 100 ; m++) {
				aa *= a;
				if (aa >= MAX || aa <= -1) {
					break;
				}
				l.add((int)aa);
			}
		}

		int cnt = 0;
		boolean[] met = new boolean[MAX];
		for (int a : l) {
			for (int b : l) {
				int ab = a + b;
				if (lowerBound <= ab && ab <= upperBound) {
					if (!met[ab]) {
						met[ab] = true;
						cnt++;
					}
				}
			}
		}
		return cnt;
	}
}

SRM 350 StarsInGraphs

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

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

  • まず、全頂点のstar numberを求める。
  • 「今どこにいるか」を状態としたダイクストラをする
    • 経由頂点数が100を超えるようだったらループしてるので、-1を返す。
  • 練習ではDPの更新部分でバグっててWAした。
import java.math.BigInteger;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class StarsInGraphs {
	class State {
		int now;
		int prev;
		int cnt;
		State(int n, int p, int c) {
			now = n;
			prev = p;
			cnt = c;
		}
	}
	
	int len;
	boolean[][] graph;
	boolean[] done;
	long[] star;
	
	public int starryPaths(String[] adj, int C) {
		len = adj.length;
		graph = new boolean[len][len];
		int[] deg = new int[len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				graph[i][j] = (adj[i].charAt(j) == '1');
				if (graph[i][j]) {
					deg[i]++;
				}
			}
		}
		
		
		long[][] ncr = new long[51][51];
		for (int i = 0 ; i < 51 ; i++) {
			ncr[i][0] = 1;
			ncr[i][i] = 1;
			for (int j = 1 ; j < i ; j++) {
				ncr[i][j] = ncr[i-1][j] + ncr[i-1][j-1];
			}
		}
		
		
		star = new long[len+1];
		for (int i = 0 ; i < len ; i++) {
			long s = 0;
			for (int d = 3 ; d <= deg[i] ; d++) {
				s += ncr[deg[i]][d];
				if (s <= -1) {
					s = -1;
					break;
				} else if (s > C) {
					s = -1;
					break;
				}
			}
			if (1 <= s && s <= C) {
				star[i] = s;
			} else {
				star[i] = -1;
			}
		}
		
		Queue<State> q = new PriorityQueue<State>(10000, new Comparator<State>(){
			public int compare(State o1, State o2) {
				return o2.cnt - o1.cnt;
			}
		});
		int[] dp = new int[len];
		for (int i = 0 ; i < len ; i++) {
			if (star[i] >= 1) {
				dp[i] = 1;
				q.add(new State(i, i, 1));
			}
		}
		
		int max = 0;
		while (q.size() >= 1) {
			State s = q.poll();
			max = Math.max(max, s.cnt);
			for (int i = 0 ; i < len ; i++) {
				if (i != s.prev && graph[s.now][i] && star[i] >= star[s.now]) {
					if (dp[i] < s.cnt + 1) {
						dp[i] = s.cnt + 1;
						if (dp[s.now] >= 100) {
							return -1;
						}
						q.add(new State(i, i, s.cnt + 1));
					}
				}
			}
		}
		return max;
	}
}

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 CoinsExchange

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

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

  • 貪欲法
    • 足りないGold、Silver、Bronzeの順に両替を行いながら埋め合わせる
  • 通ったのがいいがきれいな実装ができなかったので後で確認する。
public class CoinsExchange {
	public int countExchanges(int G1, int S1, int B1, int G2, int S2, int B2) {
		int req = 0;
		if (G2 > G1) {
			int gneed = G2 - G1;
			if (S1 >= 11 * gneed) {
				req += gneed;
				S1 -= 11 * gneed;
			} else {
				int sneed = 11 * gneed - S1;
				if (B1 >= 11 * sneed) {
					req += sneed;
					req += gneed;
					B1 -= 11 * sneed;
					S1 += sneed;
					S1 -= 11 * gneed;
				} else {
					return -1;
				}
			}
		}
		
		if (S2 > S1) {
			int sneed = S2 - S1;
			if (G1 - G2 > 0) {
				int lgold = G1 - G2;
				int needgold = (sneed + 8) / 9;
				if (lgold >= needgold) {
					req += needgold;
					G1 -= needgold;
					S1 += needgold * 9;
				} else {
					req += lgold;
					G1 = G2;
					S1 += lgold * 9;
				}
			}
			if (S2 > S1) {
				sneed = S2 - S1;
				if (B1 >= 11 * sneed) {
					req += sneed;
					B1 -= 11 * sneed;
					S1 += sneed;
				} else {
					return -1;
				}
			}
		}
		
		
		if (B2 > B1) {
			int needbronze = B2 - B1;
			int reqsilver = (needbronze + 8) / 9;
			req += reqsilver;
			if (S1 - S2 >= reqsilver) {
			} else {
				reqsilver -= (S1 - S2); 
				int reqgold = (reqsilver + 8) / 9;
				if (G1 - G2 >= reqgold) {
					req += reqgold;
				} else {
					return -1;
				}
			}
		}	
		return req;
	}
}

SRM 351 BoxesArrangement

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

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

  • 要は、A,B,Cをルールに則り並び替えた時元の位置と一致する最大数が分かればいい
    • 普通に数を並べるDPで書ける。
    • [Aを使った数][Bを使った数][Cを使った数][直前の文字][直前の文字が何個連続したか]
      • 多めに見積もって 51*51*51*4*4 = 2M程度。
  • 練習ではメモ化再帰で書こうとした
    • (文字数) >= 30 程度になると間に合わなくなったのでループDPに書き換え。
import java.util.Arrays;

public class BoxesArrangement {

	int[][][][][] memo = new int[51][51][51][4][4];
	int len;
	int[] otehon;
	int INF = 999999;
	int[] da = {1, 0, 0};
	int[] db = {0, 1, 0};
	int[] dc = {0, 0, 1};
	int[] ch;
	
	public int dfs(int a, int b, int c, int prev, int cont) {
		if (cont >= 3) {
			return INF;
		}
		if (memo[a][b][c][prev][cont] < INF) {
			return memo[a][b][c][prev][cont];
		}
		
		int ret = INF;
		int idx = (ch[0] - a) + (ch[1] - b) + (ch[2] - c);
		
		for (int d = 0 ; d < 3 ; d++) {
			int diff = (otehon[idx] == d) ? 0 : 1;
			int ta = a - da[d];
			int tb = b - db[d];
			int tc = c - dc[d];
			if (ta < 0 || tb < 0 || tc < 0) {
				continue;
			}
			if (prev == d) {
				ret = Math.min(ret, dfs(ta, tb, tc, d, cont+1) + diff);
			} else {
				ret = Math.min(ret, dfs(ta, tb, tc, d, 1) + diff);
			}
		}
		return ret;
	}
	
	public int maxUntouched(String boxes) {
		len = boxes.length();
		otehon = new int[len];
		ch = new int[3];
		for (int i = 0 ; i < len ; i++) {
			ch[boxes.charAt(i)-'A']++;
			otehon[i] = boxes.charAt(i)-'A';
		}
		for (int i = 0 ; i < 51 ; i++) {
			for (int j = 0 ; j < 51 ; j++) {
				for (int k = 0 ; k < 51 ; k++) {
					for (int l = 0 ; l < 4 ; l++) {
						Arrays.fill(memo[i][j][k][l], INF);
					}
				}
			}
		}
		memo[0][0][0][3][0] = 0;
		for (int i = 0 ; i <= ch[0] ; i++) {
			for (int j = 0 ; j <= ch[1] ; j++) {
				for (int k = 0 ; k <= ch[2] ; k++) {
					int idx = i + j + k;
					if (idx >= len) {
						continue;
					}
					for (int l = 0 ; l < 4 ; l++) {
						for (int cont = 0 ; cont < 3 ; cont++) {
							if (memo[i][j][k][l][cont] >= INF) {
								continue;
							}
							int base = memo[i][j][k][l][cont];
							
							for (int d = 0 ; d < 3 ; d++) {
								int diff = (otehon[idx] == d) ? 0 : 1;
								int tocont = ((l == d) ? cont + 1 : 1);
								memo[i+da[d]][j+db[d]][k+dc[d]][d][tocont] = Math.min(memo[i+da[d]][j+db[d]][k+dc[d]][d][tocont], base + diff);
							}
						}
					}
				}
			}
		}
		
		int ret = INF;
		for (int l = 0 ; l < 4 ; l++) {
			for (int cont = 0 ; cont < 3 ; cont++) {
				ret = Math.min(memo[ch[0]][ch[1]][ch[2]][l][cont], ret);
			}
		}	
		return (ret == INF) ? -1 : (len - ret);
	}
}

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

SRM 352 NumberofFiboCalls

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

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

  • やるだけ
    • 練習では配列のサイズ指定ミスでREをくらう
public class NumberofFiboCalls {
	public int[] fiboCallsMade(int n) {
		int[][] ret = new int[41][2];
		ret[0][0] = 1;
		ret[0][1] = 0;
		ret[1][0] = 0;
		ret[1][1] = 1;
		
		for (int k = 2 ; k <= n ; k++) {
			ret[k][0] = ret[k-1][0] + ret[k-2][0];
			ret[k][1] = ret[k-1][1] + ret[k-2][1];
		}
		return ret[n];
	}
}

SRM 352 FibonacciKnapsack

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

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

  • メモ化再帰。
    • 枝刈りを仕込むとうまくいく。
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class FibonacciKnapsack {

	class Item implements Comparable<Item> {
		long w;
		long v;
		Item(long _w, long _v) {
			w = _w;
			v = _v;
		}
		public int compareTo(Item arg0) {
			if (w == arg0.w) {
				return Long.signum(arg0.v - v);
			}
			return Long.signum(arg0.w - w);
		}
	}
	
	Item[] it;
	long[] sumw;
	long[] sumv;
	
	Map<Long, Long> m[];
	
	public long dfs(int i, long now) {
		if (i >= it.length) {
			return 0;
		}
		if (m[i].containsKey(now)) {
			return m[i].get(now);
		}
		
		long ret = 0;
		if (now >= sumw[i]) {
			ret = sumv[i];
		} else {
			ret = Math.max(ret, dfs(i+1, now));
			if (now >= it[i].w) {
				ret = Math.max(ret, dfs(i+1, now - it[i].w) + it[i].v);
			}
		}
		
		m[i].put(now, ret);
		return ret;
	}
	
	public long maximalCost(String[] items, String C) {
		int len = items.length;
		it = new Item[len];
		for (int i = 0 ; i < len ; i++) {
			String[] data = items[i].split(" ");
			long a = Long.valueOf(data[0]);
			long b = Long.valueOf(data[1]);
			it[i] = new Item(a, b);
		}
		Arrays.sort(it);
		
		sumw = new long[len+1];
		sumv = new long[len+1];
		for (int i = 0 ; i < len ; i++) {
			long v = 0;
			long w = 0;
			for (int j = i ; j < len ; j++) {
				w += it[j].w;
				v += it[j].v;
			}
			sumw[i] = w;
			sumv[i] = v;
		}
		
		m = new Map[len];
		for (int i = 0 ; i < len ; i++) {
			m[i] = new HashMap<Long, Long>();
		}

		return dfs(0, Long.valueOf(C));
	}
}