TopCoder SRM 536(2012/03/07)

メモ

MergersDivOne

貪欲法でも解くことができるが，自信がなかったのでDP．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class MergersDivOne{
	int INF=1<<28;

	public double findMaximum(int[] a){
		int n=a.length;
		sort(a);
		double[] dp=new double[n];
		fill(dp, -INF);
		dp[0]=a[0];
		for(int j=1; j<n; j++){
			double sum=dp[j-1];
			int count=1;
			for(int i=j; i<n; i++){
				sum+=a[i];
				count++;
				dp[i]=max(dp[i], sum/count);
			}
		}
		return dp[n-1];
	}
}

RollingDiceDivOne

サンプルを20~30個生成して規則を導き出した．
本番では降順でソートしていたが，ソートする必要もない解法だった．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class RollingDiceDivOne{
	public long mostLikely(int[] a){
		int n=a.length;
		long left, right;
		left=1;
		right=a[0];
		for(int j=1; j<n; j++){
			long d=right-left+1;
			if(a[j]<=d){
				left+=a[j];
				right=left+d-a[j];
			}else{
				left=left+d+(abs(a[j]-d))/2;
				if(abs(a[j]-d)%2==0){
					right=left;
				}else{
					right=left+1;
				}
			}
		}
		return left;
	}
}

Result

oo- +0/-0 407.87pts. 121st
1635 -> 1732