Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-05SRM300台を練習していく part7

SRM 313 CrazyRunning

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

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

まったく分からなかった。editorial見て実装


public class CrazyRunning {

	public double first;
	public double others;
	
	public double[] memo;
	
	public double EPSILON = 0.0000000000000001;
	
	public double rec(int total, int left) {
		if (left == 0) {
			return -others;
		}
		if (memo[left] != 0) {
			return memo[left];
		}
		
		double ans = 0.0d;
		double pp = 1.0d;
		double p0 = (double) left / (total - 1);
		double p1 = (double) (total - left - 2) / (total - 1);
		double p2 = 1.0d / (total - 1);
		double p20 = p2 * left / (total - 1);
		double p21 = p2 * (total - 1 - left) / (total - 1);

		while (pp > EPSILON) {
			ans += pp * p0 * (others * 2 + rec(total, left-1));
			ans += pp * p20 * (first * 2 + others * 2 + rec(total, left-1));
			ans += pp * p1 * (others * 2);
			ans += pp * p21 * (first * 2 + others * 2);
			pp *= (p1 + p21);
		}
		memo[left] = ans;
				
		return ans;
	}
	
	public double expectedTime(int[] corridors) {
		int len = corridors.length;

		first = corridors[0];
		for (int i = 1 ; i < len ; i++) {
			others += corridors[i];
		}
		others = others / (double)(len - 1);
		memo = new double[100];
				
		return first + others * 2 + rec(len, len-2);
	}

}

SRM 310 FloatingMedian

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

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

ソート済みのlistに対してはCollections.binarySearchが使えるので、

インデックスをずらす際に取り除く値の位置と、新しくリストに挿入する値の位置を二分探索で探してあげる。


import java.util.ArrayList;
import java.util.List;

public class FloatingMedian {

	public long sumOfMedians(int seed, int mul, int add, int N, int K) {
		long[] nums = new long[N];
		nums[0] = seed;
		for (int i = 1 ; i < N ; i++) {
			nums[i] = ((1L * nums[i-1] * mul + add) % 65536);
		}
		List<Long> ls = new ArrayList<Long>();
		for (int i = 0 ; i < K ; i ++) {
			ls.add(nums[i]);
		}
		java.util.Collections.sort(ls);

		long med = ls.get((K+1)/2-1);
		
		for (int i = 0 ; i < N - K ; i++) {
			int rem = java.util.Collections.binarySearch(ls, nums[i]);
			ls.remove(rem);
			int ins = java.util.Collections.binarySearch(ls, nums[i+K]);
			if (ins < 0) {
				ins = -ins - 1;
			}
			ls.add(ins, nums[i+K]);
			med += ls.get((K+1)/2-1);
		}

		return med;
	}

}

SRM 315 SillySudoku

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

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

意外とやるだけ問題だった。


public class SillySudoku {

	public int[][] perm = {
		{1, 2, 3, 4},
		{1, 2, 4, 3},
		{1, 3, 2, 4},
		{1, 3, 4, 2},
		{1, 4, 2, 3},
		{1, 4, 3, 2},

		{2, 1, 3, 4},
		{2, 1, 4, 3},
		{2, 3, 1, 4},
		{2, 3, 4, 1},
		{2, 4, 1, 3},
		{2, 4, 3, 1},

		{3, 2, 1, 4},
		{3, 2, 4, 1},
		{3, 1, 2, 4},
		{3, 1, 4, 2},
		{3, 4, 2, 1},
		{3, 4, 1, 2},

		{4, 2, 3, 1},
		{4, 2, 1, 3},
		{4, 3, 2, 1},
		{4, 3, 1, 2},
		{4, 1, 2, 3},
		{4, 1, 3, 2},
	};

	public int[][] map;
	public int[][] dmap;
	public int ans = 0;

	public boolean isok() {
		for (int i = 0 ; i < 4 ; i++) {
			int d = 1;
			for (int j = 0 ; j < 4 ; j++) {
				d *= dmap[j][i];
			}
			if (d != 24) {
				return false;
			}
		}

		int[] dx = {0, 2, 0, 2};
		int[] dy = {0, 0, 2, 2};
		for (int d = 0 ; d < 4 ; d++) {
			int dd = dmap[dx[d]][dy[d]] * dmap[dx[d]][1+dy[d]] * dmap[dx[d]+1][dy[d]] * dmap[1+dx[d]][1+dy[d]];
			if (dd != 24) {
				return false;
			}
		}
		return true;
	}

	public void bf(int rec) {
		if (rec == 4) {
			if (isok()) {
				ans++;
			}
			return;
		}
		for (int x = 0 ; x < 24 ; x++) {
			boolean isok = true;
			for (int i = 0 ; i < 4 ; i++) {
				dmap[rec][i] = perm[x][i];
				if (map[rec][i] != 0 && dmap[rec][i] != map[rec][i]) {
					isok = false;
					break;
				}
			}
			if (isok) {
				bf(rec + 1);
			}
		}
	}

	public int countWays(String[] board) {
		map = new int[4][4];
		dmap = new int[4][4];
		for (int i = 0 ; i < 4 ; i++) {
			for (int j = 0 ; j < 4 ; j++) {
				if (board[i].charAt(j) != '-') {
					map[i][j] = board[i].charAt(j) - '0';
				}
			}
		}

		bf(0);
		return ans;
	}
}

SRM 315 DigitsSum

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

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

足してmod 9するだけ。


public class DigitsSum {

	public int lastDigit(int n) {
		if (n == 0) {
			return 0;
		}
		int n9 = 0;
		while (n > 0) {
			n9 += n % 10;
			n /= 10;
		}

		if (n9 % 9 == 0) {
			return 9;
		}
		return n9 % 9;
	}

}




SRM 316 PlacingPieces

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

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

難しい。解いたのはだいぶ前だけど今やれって言われたら多分出来ない


public class PlacingPieces {

	public int optimalPlacement(int L, int[] pieces) {
		java.util.Arrays.sort(pieces);
		int len = pieces.length;
		int ans = len;
		if (pieces[0] > L) {
			return 0;
		}

		for (int p = 0 ; p < len ; p++) {
			boolean[][][] dp = new boolean[31][31][1001];
			int inilen = 0;
			for (int i = 0 ; i < p ; i++) {
				inilen += pieces[i];
			}
			if (inilen >= L) {
				break;
			}
			dp[p][p][inilen] = true;
			for (int i = 0 ; i < len ; i++) {
				for (int n = 0 ; n <= len ; n++) {
					for (int l = 0 ; l <= L ; l++) {
						if (dp[i][n][l]) {
							dp[i+1][n][l] = true;
							if (p != i && l + pieces[i] <= L) {
								dp[i+1][n+1][l+pieces[i]] = true;
							}
						}
					}
				}
			}

			for (int n = 0 ; n <= len ; n++) {
				for (int l = L ; l >= 0 ; l--) {
					if (dp[len][n][l] && L-l < (n+1)*pieces[p]) {
						ans = Math.min(ans, n);
					}
				}
			}
		}
		return ans;
	}
}

SRM 316 InboxCleanup

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

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

シミュレーションやるだけ。


public class InboxCleanup {

	public int fewestClicks(String messages, int low, int high) {
		int ct = Integer.MAX_VALUE;
		int len = messages.length();
		for (int per = low ; per <= high ; per++) {
			int clicks = 0;
			int last = (len - 1) / per;
			for (int i = 0 ; i <= last ; i++) {
				String m = "";
				if (i == last) {
					m = messages.substring(i * per);
				} else {
					m = messages.substring(i * per, (i+1) * per);
					clicks++;
				}
				int sp = 0;
				for (int ma = 0 ; ma < m.length() ; ma++) {
					if (m.charAt(ma) == 'D') {
						sp++;
					}
				}
				if (sp >= 1) {
					clicks += 1 + Math.min(1 + m.length() - sp, sp);
				}
			}
			ct = Math.min(ct, clicks);
		}
		return ct;
	}
}