Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-06SRM300台を練習していく part8

SRM 321 Chocolate

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

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

長方形でない形には分割できないので、 x * y = nTiles となる形に分割できるかどうか考える。分割は高々2回。

x か y のどちらかが width もしくは height と等しければ分割は1回で済む。


public class Chocolate {

	public int minSplitNumber(int width, int height, int nTiles) {
		if (1L * width * height == (long)nTiles) {
			return 0;
		}
		
		int root = (int)Math.sqrt(nTiles);
		int mintry = 9999999;
		for (int x = 1 ; x <= root ; x++) {
			if (nTiles % x == 0) {
				int y = nTiles / x;
				if ((x < width && y < height) || (x < height && y < width)) {
					mintry = Math.min(mintry, 2);
				}
				if ((x == width && y < height) || (x == height && y < width)) {
					mintry = Math.min(mintry, 1);					
				}
				if ((x < width && y == height) || (x < height && y == width)) {
					mintry = Math.min(mintry, 1);					
				}
			}
		}
		
		if (mintry == 9999999) {
			mintry = -1;
		}
		return mintry;
	}

}

SRM 319 ConstructBST

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

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

二分探索木を作って、各ノードの左の子と右の子の数をカウント。

再帰的に重複組み合わせを計算していく。


import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class ConstructBST {

	Map<Integer, Tree> memo = new HashMap<Integer, Tree>();
	
	class Tree {
		Tree left;
		Tree right;
		int value = 0;
		long s = 0;
		int cl = 0;
		int cr = 0;
		
		public Tree(int v) {
			value = v;
		}
		
		public void putnew(int v) {
			if (v < value) {
				cl++;
				if (left == null) {
					left = new Tree(v);
				} else {
					left.putnew(v);
				}
			} else {
				cr++;
				if (right == null) {
					right = new Tree(v);
				} else {
					right.putnew(v);
				}				
			}
		}
		
		public int countChild() {
			int l = 0, r = 0;
			if (left != null) {
				l = left.countChild();
			}
			if (right != null) {
				r = right.countChild();
			}
			cl = l;
			cr = r;
			return l + r + 1;
		}
		
		public void display() {
			if (left != null) {
				left.display();
			}
			if (right != null) {
				right.display();
			}
		}
	}
	
	public long hp(int n, int m) {
		BigInteger v = BigInteger.valueOf(1);
		for (long l = n + m ; l >= n + 1 ; l--) {
			v = v.multiply(BigInteger.valueOf(l));
		}
		for (long l = m ; l >= 2 ; l--) {
			v = v.divide(BigInteger.valueOf(l));
		}
		return v.longValue();
	}
	
	public long dfs(Tree t) {
		if (t.left == null && t.right == null) {
			return 1;
		}
		if (t.left == null) {
			return dfs(t.right);
		}
		if (t.right == null) {
			return dfs(t.left);
		}
		return dfs(t.right) * dfs(t.left) * hp(t.cl, t.cr);
	}
	
	public void put(int value) {
		boolean isleft = (value % 2 == 0);
		Tree parent = memo.get(value / 2);
		if (parent != null) {
			Tree child = new Tree(value);
			if (isleft) {
				parent.left = child;
			} else {
				parent.right = child;
			}
			memo.put(value, child);
		}
	}

	public long numInputs(int[] tree) {
		java.util.Arrays.sort(tree);
		Tree root = new Tree(1);
		memo.put(1, root);
		for (int i = 1 ; i < tree.length ; i++) {
			put(tree[i]);
		}
		root.countChild();

		return dfs(root);
	}
}



SRM 320 ExtraordinarilyLarge

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

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

x, yの末尾についている階乗(!)の数をカウントし、同数だけ取り除く。(x! = y! なら x = y だから)

そして 0! = 1に注意してシミュレーション。


import java.math.BigInteger;

public class ExtraordinarilyLarge {

	public int compareMultiply(int times, BigInteger basex, BigInteger basey) {
		for (int yp = 0 ; yp < times ; yp++) {
			BigInteger cy = BigInteger.valueOf(basey.longValue());
			if (basey.longValue() == 0) {
				cy = BigInteger.valueOf(1);
			} else {
				for (long v = basey.longValue() - 1 ; v >= 2 ; v--) {
					cy = cy.multiply(BigInteger.valueOf(v));
					if (cy.compareTo(basex) > 0) {
						yp = times;
						break;
					}
				}
			}
			basey = cy.abs();
		}
		return basex.compareTo(basey);
	}
	
	public String compare(String x, String y) {
		int xx = 0, yy = 0;
		for (int l = x.length() - 1 ; l >= 0 ; l--) {
			if (x.charAt(l) == '!') {
				xx++;
			}
 		}
		for (int l = y.length() - 1 ; l >= 0 ; l--) {
			if (y.charAt(l) == '!') {
				yy++;
			}
 		}
		int removes = Math.min(xx, yy);
		long lbasex = Long.valueOf(x.substring(0, x.length() - xx));
		long lbasey = Long.valueOf(y.substring(0, y.length() - yy));
		if (lbasex == 0 && xx > 0) {
			lbasex = 1;
		}
		if (lbasey == 0 && yy > 0) {
			lbasey = 1;
		}
		
		BigInteger basex = BigInteger.valueOf(lbasex);
		BigInteger basey = BigInteger.valueOf(lbasey);
		xx -= removes;
		yy -= removes;
		int cp = -2;
		if (xx == 0 && yy == 0) {
			cp = basex.compareTo(basey);
		}
		if (xx == 0) {
			cp = compareMultiply(yy, basex, basey);
		}
		if (yy == 0) {
			cp = compareMultiply(xx, basey, basex) * -1;
		}
		if (cp == -1) {
			return "x<y";
		} else if (cp == 0) {
			return "x=y";
		} else {
			return "x>y";
		}
	}
}



SRM 319 BusSeating

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

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

各空席の位置を座標に変換して、組み合わせを全探索。


public class BusSeating {

	public double getArrangement(String leftRow, String rightRow) {
		int ptnum = 0;
		int[] px = new int[20];
		int[] py = new int[20];
		
		for (int i = 0 ; i < 10 ; i++) {
			if (leftRow.charAt(i) == '-') {
				px[ptnum] = i;
				py[ptnum] = 0;
				ptnum++;
			}
			if (rightRow.charAt(i) == '-') {
				px[ptnum] = i;
				py[ptnum] = 2;
				ptnum++;
			}
		}
		
		double min = 999999999.9d;
		for (int a = 0 ; a < ptnum ; a++) {
			for (int b = a+1 ; b < ptnum ; b++) {
				for (int c = b+1 ; c < ptnum ; c++) {
					double ab = Math.hypot(px[a] - px[b], py[a] - py[b]);
					double bc = Math.hypot(px[b] - px[c], py[b] - py[c]);
					double ca = Math.hypot(px[c] - px[a], py[c] - py[a]);
					if (ab + bc + ca < min) {
						min = ab + bc + ca;
					}
				}
			}
		}
		if (min >= 999999999) {
			return 0;
		}
		return min;
	}
}



SRM 320 ContestSchedule

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

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

コンテストを終わりの早い順に並び替え、DPするだけ


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

public class ContestSchedule {

	
	class Contest {
		long s, e;
		double p;
		public Contest(String[] param) {
			s = Long.valueOf(param[0]);
			e = Long.valueOf(param[1]);
			p = Integer.valueOf(param[2]) * 1.0d / 100;
		}

		public String toString() {
			return s + "-" + e + ":" + p;
		}
	}
	
	List<Contest> conts = new ArrayList<Contest>();
	
	Map<Integer, Map<Long, Double>> memo = new HashMap<Integer, Map<Long, Double>>();
	
	public double dfs(int i, long time) {
		double ans = 0.0d;
		if (i >= conts.size()) {
			return ans;
		}
		if (memo.get(i).containsKey(time)) {
			return memo.get(i).get(time);
		}
		
		Contest c = conts.get(i);
		
		ans = dfs(i+1, time);
		if (time <= c.s) {
			ans = Math.max(ans, dfs(i+1, c.e) + c.p);
		}
		memo.get(i).put(time, ans);
		
		return ans;
	}
	
	
	public double expectedWinnings(String[] contests) {
		int len = contests.length;
		for (String cont : contests) {
			conts.add(new Contest(cont.split(" ")));
		}
		java.util.Collections.sort(conts, new Comparator<Contest>() {
			public int compare(Contest a, Contest b) {
				return (int)(a.e - b.e);
			}
		});
		for (int i = 0 ; i <= len ; i++) {
			memo.put(i, new HashMap<Long, Double>());
		}
		
		return dfs(0, 0);
	}

}




SRM 318 CyclicGame

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

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


public class CyclicGame {
	
	public double EPSILON = 0.00000000000001;
	
	public double[][] _memo;
	
	public int[] _cells;
	
	public double dfs(int times, int now) {
		if (times >= 1000) {
			return 0.0d;
		}
		if (_memo[times][now] >= 0) {
			return _memo[times][now];
		}
		
		double exp = 0.0d;
		for (int d = 1 ; d <= 6 ; d++) {
			int toidx = (now + d) % _cells.length;
			int val = _cells[toidx];
			exp += val * 1.0d / Math.pow(6, times) + dfs(times + 1, toidx);
		}
		
		if (exp < 0.0d) {
			exp = 0.0d;
		}
		
		_memo[times][now] = exp;
		return exp;
	}

	public double estimateBank(int[] cells) {
		_cells = cells;
		_memo = new double[1000][15];
		for (int t = 0 ; t < 1000 ; t++) {
			for (int m = 0 ; m < 15 ; m++) {
				_memo[t][m] = -1;
			}
		}
		return dfs(1, 0);
	}
}



SRM 305 InterleavePal

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

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


public class InterleavePal {

	String _s, _t;
	int _max;
	
	boolean[][][][] memo;
	
	public void dfs(int ss, int se, int ts, int te) {
		int len = (se - ss) + (te - ts);
		if (_max < len) {
			_max = len;
		}
		
		if (memo[ss][se][ts][te]) {
			return;
		}
		
		if (ss >= 1) {
			if (se < _s.length() && _s.charAt(ss-1) == _s.charAt(se)) {
				dfs(ss-1, se+1, ts, te);
			}
			if (te < _t.length() && _s.charAt(ss-1) == _t.charAt(te)) {
				dfs(ss-1, se, ts, te+1);
			}
		}

		if (ts >= 1) {
			if (se < _s.length() && _t.charAt(ts-1) == _s.charAt(se)) {
				dfs(ss, se+1, ts-1, te);
			}
			if (te < _t.length() && _t.charAt(ts-1) == _t.charAt(te)) {
				dfs(ss, se, ts-1, te+1);
			}
		}
		memo[ss][se][ts][te] = true;
	}

	public int longestPal(String s, String t) {
		_s = s;
		_t = t;
		memo = new boolean[51][51][51][51];
		for (int ss = 0 ; ss <= _s.length() ; ss++) {
			for (int tt = 0 ; tt <= _t.length() ; tt++) {
				dfs(ss, ss, tt, tt);
				if (ss != _s.length()) {
					dfs(ss, ss+1, tt, tt);
				}
				if (tt != _t.length()) {
					dfs(ss, ss, tt, tt+1);
				}
			}			
		}
		return _max;
	}
}