ProjectEuler Problem 398 Cutting rope - uwicoder

リンク

http://projecteuler.net/problem=398

問題概要

長さnのロープの整数点n-1個のうち相異なるm-1個を等確率ランダムに選んで切るとき、短い方から2番目の長さの断片の長さの期待値を求めよ。

制約

n=10^7, m=100

状態

Solved(Java) 2h 3rd

ポイント

連続と近い。やり方は全然違うが

解き方

...

まず一番短い断片の長さがaとなる確率を求めると、それはすべてがa以上のものからすべてがa+1以上のものの個数を引けばいいので
で表される。これを前提に2番目の長さのそれぞれの確率を求める。
2番目の長さをbとする。a<bのときは、"a(>=b)(>=b)..."から"a(>=b+1)(>=b+1)..."を引いて、aの位置分(m)をかければ良い。よって、
とおり。分母は上記の分母と同じ。
a=bのときは、すべてがa以上のものから"a(>=a+1)(>=a+1)..."を引けばよいので、
とおり。あとはこれを分母でわって、bの値をかけて総和を求めれば良い。
愚直に計算するとO((n/m)^2*m)程度かかってしまう。有効な(a,b)の組は少ないので定数倍は小さくなっているが、これでも時間がかかる。combinationの計算でO(m)かかっているのをO(1)にする。aが1個下がるとbのときのcombのn部は1ずつ下がっていくため、m個掛ける必要はなく、1度求めた値に1かけ1わりするだけでよい。たとえばに対してはa-1のときの値に(n-a-b(m-1)+m-2-(m-2)+1)をかけ(n-(a-1)-b(m-1)+m-2)を割れば良い。
これによりO(n/m*m)=O(n)でいける。またaの大きいところでは出てくる期待値は非常に小さいので、10^7,100の場合だとa=20000程度からの下降だけでいける。

コード

...

package p350;
import java.math.BigInteger;
import java.util.Arrays;
 
// 116
// 125
// 134
// 143
public class P398_7 {
 
 
	public static void solve()
	{
		int n = 20, m = 4;
//		int n = 3, m = 2;
		double S = 0;
		double prevw = 0;
		double[] vs = new double[120001];
		Arrays.fill(vs, -1);
 
		for(int a = n/m+1;a >= 1;a--){
//			for(int a = 20000;a >= 1;a--){
			tr(a);
			double w = 1;
			for(int i = 0;i < m-1;i++){
				w = w / (n-1-i) * (n-a*m+m-1-i);
			}
			double all = w - prevw;
			prevw = w;
 
			double prev = all;
			int b;
			for(b = a+1;b*(m-1)+a<=n;b++){
				double v;
				if(vs[b] == -1){
					v = (m-1)*m/(double)(n-1);
					for(int i = 0;i < m-2;i++){
						v = v / (n-1-1-i) * (n-a-b*(m-1)+m-2-i);
					}
					vs[b] = v;
				}else{
					vs[b] = vs[b] * (n-a-b*(m-1)+m-2-0) / (n-a-b*(m-1)+m-2-(m-2));
					v = vs[b];
				}
				S += (prev - v) * (b-1);
				prev = v;
			}
			S += prev * (b-1);
			tr(S);
		}
		tr(S);
	}
 
	static BigInteger b(long n){ return BigInteger.valueOf(n); }
 
	static BigInteger C(long n, long r)
	{
		if(n < 0 || r < 0 || n < r)return BigInteger.ZERO;
		BigInteger ret = BigInteger.ONE;
		for(int i = 1;i <= r;i++){
			ret = ret.multiply(b(n-i+1)).divide(b(i));
		}
		return ret;
	}
 
	public static void main(String[] args) {
		long s = System.currentTimeMillis();
		solve();
		long g = System.currentTimeMillis();
		tr(g-s+"ms");
	}
 
	static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}