Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-19SRM370 (Practice)

hardは典型っぽい問題だけど好き 293/561位 半分以下爆死

問題結果ポイントその他
250DrawingMarblesAccepted243.30確率
500ConnectTheCitiesWA0.00二分探索+DP
1000NumberOfDivisorsWA0.00数論+DP

SRM 370 DrawingMarbles

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

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

  • 数学。
    • 各色について確率を計算し、足し合わせる。
    • colors[i] < n の場合に注意する。
public class DrawingMarbles {

	public double sameColor(int[] colors, int n) {
		int len = colors.length;
		double prob = 0.0d;
		int sum = 0;
		for (int i = 0 ; i < len ; i++) {
			sum += colors[i];
		}
		
		for (int i = 0 ; i < len ; i++) {
			int nsum = sum;
			int target = colors[i];
			double pr = 1.0d;
			if (target >= n) {
				for (int p = 0 ; p < n ; p++) {
					pr *= (double) target / nsum;
					target--;
					nsum--;
				}
				prob += pr;
			}
		}
		
		return prob;
	}
}

SRM 370 ConnectTheCities

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

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

  • dp[使った数][前回の位置][最大距離]で考えてみたがWA
    • 距離を決め打ちし二分探索するのが正解らしい
    • あとでちゃんと通す
  • 直した。
    • DPでも通る。終端の処理が間違ってた。
import java.util.Arrays;

public class ConnectTheCities {
	public int minimalRange(int distance, int funds, int[] position) {
		Arrays.sort(position);
		int len = position.length;
		
		int[][][] dp = new int[len+1][distance+1][distance+1];
		for (int i = 0 ; i <= len ; i++) {
			for (int pos = 0 ; pos <= distance ; pos++) {
				Arrays.fill(dp[i][pos], Integer.MAX_VALUE);
			}
		}
		dp[0][0][0] = 0;
		
		for (int i = 0 ; i < len ; i++) {
			for (int pos = 0 ; pos <= distance ; pos++) {
				for (int mxdist = 0 ; mxdist <= distance ; mxdist++) {
					if (dp[i][pos][mxdist] == Integer.MAX_VALUE) {
						continue;
					}
					for (int go = pos ; go <= distance ; go++) {
						int money = Math.abs(go - position[i]);
						int dist = mxdist;
						if (go >= pos) {
							dist = Math.max(go - pos, mxdist);
						}
						dp[i+1][go][dist] = Math.min(dp[i+1][go][dist], dp[i][pos][mxdist] + money);
					}
				}
			}
		}

		int dost = distance;
		for (int pos = 0 ; pos <= distance ; pos++) {
			for (int mxdist = 0 ; mxdist <= distance ; mxdist++) {
				if (dp[len][pos][mxdist] <= funds) {
					dost = Math.min(Math.max(distance - pos, mxdist), dost);
				}
			}
		}
		return dost;
	}

}

SRM 370 NumberOfDivisors

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

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

  • 約数がちょうどk個の数の中で、最小のものを求める
    • p={2,3,5,7, ... } を素数の列とする。
    • A = p1^a1*p2^a2* ... * pn^an と素因数分解できるとき、約数の個数は (1+a1) * (1+a2) * ... * (1 + an)個
    • [掛け算の結果][素数をどこまで使ったか]の最小値でDPする
    • 素数は47まで考えれば十分 (2*3*5*...*53 > 10^18なので)
  • 練習ではオーバーフローしてWA
    • BigIntegerに書き換えたら通った。

p