Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-30SRM339 (Practice)

問題結果ポイントその他
250BusTripAccepted154.04実装
450TestBettingStrategyAccepted351.09確率+DP
1000RPSTournamentOpened0.00解いてない

SRM 339 BusTrip

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

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

  • 問題文のとおりにシミュレーションするだけ。
import java.util.Arrays;

public class BusTrip {
	class Bus {
		int total;
		int id;
		int[] begins;
		int[] next;
		Bus(String input, int i) {
			String[] strs = input.split(" ");
			begins = new int[101];
			next = new int[101];
			Arrays.fill(begins, -1);
			Arrays.fill(next, -1);
			int len = strs.length;
			
			total = 0;

			// total distance
			int prev =  Integer.valueOf(strs[0]);
			for (int j = 0 ; j < len ; j++) {
				int dg = Integer.valueOf(strs[j]);
				int diff = Math.abs(prev - dg);
				total += diff;
				begins[dg] = total;
				prev = dg;
			}
			total += Math.abs(prev - Integer.valueOf(strs[0]));

			// next
			for (int j = 0 ; j < len - 1 ; j++) {
				int from = Integer.valueOf(strs[j]);
				int to = Integer.valueOf(strs[j+1]);
				next[from] = to;
			}
			next[Integer.valueOf(strs[len-1])] = Integer.valueOf(strs[0]);
			
			id = i;
		}
	}

	public int returnTime(int N, String[] buses) {
		int bl = buses.length;
		Bus[] b = new Bus[bl];
		for (int i = 0 ; i < bl ; i++) {
			b[i] = new Bus(buses[i], i);
		}
		
		int time = -1;
		int now = 0;
		while (time <= 1000) {
			int bestbus = -1;
			int besttime = 100000;
			for (int i = 0 ; i < bl ; i++) {
				if (b[i].begins[now] == -1) {
					continue;
				}
				for (int c = 0 ; c < 1000 ; c++) {
					int cometime = b[i].begins[now] + b[i].total * c;
					if (cometime > time) {
						if (besttime > cometime) {
							besttime = cometime;
							bestbus = i;
						}
						break;
					}
				}
			}
			if (bestbus == -1) {
				System.out.println("err");
			}
			
			int go = b[bestbus].next[now];
			time = besttime + Math.abs(go - now);
			now = go;
			if (now == 0) {
				break;
			}
		}
		return (time >= 1001) ? -1 : time;
	}
}

SRM 339 TestBettingStrategy

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

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

  • 簡単。
public class TestBettingStrategy {

	public double winProbability(int initSum, int goalSum, int rounds, int prob) {
		if (initSum >= goalSum) {
			return 1.0d;
		}
		
		int[] bets = new int[22];
		bets[0] = 1;
		for (int i = 1 ; i < 21 ; i++) {
			bets[i] = bets[i-1] * 2;
		}
		
		double p = prob * 1.0d / 100;
		double ans = 0.0d;
		double[][][] dp = new double[51][21][2002];
		dp[0][0][initSum] = 1.0d;
		for (int r = 0 ; r < rounds ; r++) {
			for (int l = 0 ; l < 21 ; l++) {
				for (int now = 0 ; now <= 2000 ; now++) {
					if (dp[r][l][now] > 0.0d) {
						double base = dp[r][l][now];
						int bet = bets[l];
						if (now < bet) {
							continue;
						}
						
						int win = (now - bet) + bet * 2;
						if (win >= goalSum) {
							win = 2001;
						}
						int lose = now - bet;
						
						if (win >= 2001) {
							ans += base * p;
						} else {
							dp[r+1][0][win] += base * p;
						}
						dp[r+1][Math.min(20, l+1)][lose] += base * (1.0d - p);
					}
				}
			}
		}
		return ans;
	}
}