Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-30SRM356 (Practice)

問題結果ポイントその他
250AverageProblemAccepted129.30DP
550MarriageProblemRevisedRE0.00グラフ
950EscapeTheJailWA0.00一次方程式

SRM 356 AverageProblem

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

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

  • 頭の悪いDPをした
    • DPで解ける余地を残してくれるあたり優しい
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class AverageProblem {

	public int numberOfParticipants(String[] marks) {
		for (int i = 999 ; i >= 0 ; i--) {
			String zux = "0." + (String.valueOf(i) + "00000").substring(0, 3);
			System.out.print("\"" + zux + "\",");
		}
		System.out.println();
		
		Set<String> want = new HashSet<String>();
		for (String s : marks) {
			String[] data = s.split(" ");
			for (String n : data) {
				want.add(n);
			}
		}
		Map<String, Integer> smap = new HashMap<String, Integer>();
		for (String w : want) {
			smap.put(w, smap.size());
		}
		
		boolean[] dp = new boolean[10010];
		boolean[] dp_next = new boolean[10010];
		dp[0] = true;
		for (int p = 1 ; p <= 1000 ; p++) {
			for (int v = 0 ; v < 10010 ; v++) {
				if (dp[v]) {
					for (int a = 0 ; a <= 10 ; a++) {
						if (v+a < 10010) {
							dp_next[v+a] = true;
						}
					}
				}
			}
			for (int v = 0 ; v < 10010 ; v++) {
				dp[v] = dp_next[v];
				dp_next[v] = false;
			}

			boolean isok = true;
			for (String x : want) {
				int val = (int)(Double.valueOf(x) * p);
				boolean made = false;
				for (int d = 0 ; d <= 1 ; d++) {
					int intval = val + d;
					if (dp[intval]) {
						String dval = (intval * 1.0d / p) + "0000";
						if (intval == p * 10) {
							dval = dval.substring(0, 6);
						} else {
							dval = dval.substring(0, 5);
						}
						if (dval.equals(x)) {
							made = true;
							break;
						}
					}
				}
				if (!made) {
					isok = false;
					break;
				}
			}
			if (isok) {
				return p;
			}
		}
		return -1;
	}

}

SRM 356 MarriageProblemRevised

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

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

  • 二部構造が見え見えになってるが、マッチングでは解けなさそう
    • 制約が緩いしDPしちゃおう
  • でも、少なくとも [男x12が結婚したか][女x12が結婚したか] という状態が必要だから・・・
    • (2^12) ^ 2 = 16M
    • メモリが足りなくなるかも・・・
  • ダイクストラを実装したらサンプル合った。
    • 他に方法が思いつかないのでそのまま出してしまった。

SRM 356 EscapeTheJail

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

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

  • ランダムウォーク。
    • 蟻本のまんま。
  • 練習ではあえて5万移動ぐらいの計算打ち切りDPを書いてみたけどWAした
    • 多分誤差が大きくなって正しい答えがでないんだと思う
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

public class EscapeTheJail {

	int[] dx = {1, 0, -1, 0};
	int[] dy = {0, 1, 0, -1};
	
	double EPS = 0.0000000001;
	
	public double[] solve_mat(double[][] r1, double[] r2) {
		int len = r1.length;
		double[][] B = new double[len][len+1];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				B[i][j] = r1[i][j];
			}
		}
		for (int i = 0 ; i < len ; i++) {
			B[i][len] = r2[i];
		}
		
		for (int i = 0 ; i < len ; i++) {
			int pv = i;
			for (int j = i ; j < len ; j++) {
				if (Math.abs(B[j][i]) > Math.abs(B[pv][i])) {
					pv = j;
				}
			}
			double[] tmp = B[i].clone();
			B[i] = B[pv].clone();
			B[pv] = tmp;
			if (Math.abs(B[i][i]) < EPS) {
				return new double[]{};
			}
			
			for (int j = i + 1 ; j <= len ; j++) {
				B[i][j] /= B[i][i];
			}
			for (int j = 0 ; j < len ; j++) {
				if (i != j) {
					for (int k = i + 1 ; k <= len ; k++) {
						B[j][k] -= B[j][i] * B[i][k];
					}
				}
			}
		}
		
		double[] ret = new double[len];
		for (int i = 0 ; i < len ; i++) {
			ret[i] = B[i][len];
		}
		return ret;
	}
	
	public double findExit(String[] jail) {
		int h = jail.length;
		int w = jail[0].length();
		int[][] map = new int[h+2][w+2];
		
		int sx = 0, sy = 0;
		boolean[][] isgoal = new boolean[h+2][w+2];
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				if (jail[i].charAt(j) == '@') {
					sx = j;
					sy = i;
				}
				if (jail[i].charAt(j) == '$') {
					isgoal[i+1][j+1] = true;
				}
			}
		}
		
		boolean[][] cango = new boolean[h][w];
		Queue<Integer> q = new ArrayBlockingQueue<Integer>(1000);
		q.add(sy*w+sx);
		cango[sy][sx] = true;
		boolean reachable = false;
		while (q.size() >= 1) {
			int stat = q.poll();
			int nx = stat % w;
			int ny = stat / w;
			for (int d = 0 ; d < 4 ; d++) {
				int tx = nx + dx[d];
				int ty = ny + dy[d];
				if (tx < 0 || ty < 0 || tx >= w || ty >= h) {
					continue;
				}
				if (jail[ty].charAt(tx) == '.') {
					if (!cango[ty][tx]) {
						cango[ty][tx] = true;
						q.add(ty*w+tx);
					}
				} else if (jail[ty].charAt(tx) == '$') {
					reachable = true;
				}
			}
		}
		if (!reachable) {
			return -1.0d;
		}
		
		int len = h*w;
		double[][] mat = new double[len][len];
		double[] mat2 = new double[len];
		for (int i = 0 ; i < h ; i++) {
			for (int j = 0 ; j < w ; j++) {
				if (jail[i].charAt(j) == '$' || !cango[i][j]) {
					mat[i*w+j][i*w+j] = 1;
					continue;
				}
				int cnt = 0;
				for (int d = 0 ; d < 4 ; d++) {
					int tx = j + dx[d];
					int ty = i + dy[d];
					if (tx < 0 || ty < 0 || tx >= w || ty >= h) {
						continue;
					}
					if (jail[ty].charAt(tx) == '#') {
						continue;
					}
					mat[i*w+j][ty*w+tx] = -1;
					cnt++;
				}
				mat[i*w+j][i*w+j] = cnt;
				mat2[i*w+j] = cnt;
			}
		}
		
		double[] val = solve_mat(mat, mat2);
		
		return val[sy*w+sx];
	}
}