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に書き換えたら通った。

import java.math.BigInteger;
import java.util.Arrays;

public class NumberOfDivisors {
	public long smallestNumber(int k) {
		if (k <= 2) {
			return k;
		}
		int[] p = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
		int pl = p.length;
		
		long limit = (long)Math.pow(10, 18);
		BigInteger blimit = BigInteger.valueOf(limit);
		long[][] dp = new long[50001][pl+2];
		for (int i = 0 ; i < 50001 ; i++) {
			Arrays.fill(dp[i], Long.MAX_VALUE);
		}
		dp[1][0] = 1;
		for (int a = 1 ; a < k ; a++) {
			for (int b = 0 ; b < pl ; b++) {
				if (dp[a][b] != Long.MAX_VALUE) {
					for (int c = 0 ; (c+1) * a <= k ; c++) {
						if (k % ((c+1) * a) == 0) {
							if (Math.pow(p[b], c) <= 0 || Math.pow(p[b], c) > limit) {
								break;
							}
							BigInteger from = BigInteger.valueOf(dp[a][b]);
							BigInteger mul = BigInteger.valueOf((long)Math.pow(p[b], c));
							if (from.multiply(mul).compareTo(blimit) > 0){
								break;
							}
							long willgo = dp[a][b] * (long)Math.pow(p[b], c);
							dp[(c+1)*a][b+1] = Math.min(dp[a][b] * (long)Math.pow(p[b], c), dp[(c+1)*a][b+1]);
						}
					}
				}
			}
		}
		long l = Long.MAX_VALUE;
		for (int i = 1 ; i <= pl ; i++) {
			if (dp[k][i] != Long.MAX_VALUE) {
				l = Math.min(l, dp[k][i]);
			}
		}
		
		if (l == Long.MAX_VALUE || l > limit) {
			return -1;
		}
		
		return l;
	}
}