BottomCoder SRM 399 div2

http://www.topcoder.com/stat?c=round_overview&rd=12171

point	result	time
250	AC	4m
500	AC	3.5m
1000	WA1	17m

1000解いて余裕かましてたら凡ミスに気づいて直してたら終了した('A`)

250

駅(||<=50)とそれら全てをつなぐ環状線がある。隣り合う駅間の線路長t[]が与えられたとき、異なる2つの駅間の最短経路長の最大値を求めよ。

駅A,Bについて、Aのインデックス

public class CircularLine {

	public int longestTravel(int[] t) {
		
		int n = t.length;
		int max = 0;
		for(int i = 0;i < n;i++){
			for(int j = i;j < n;j++){
				max = Math.max(max, Math.min(dur(t, i, j), dur(t, j, i)));
			}
		}
		return max;
	}
	
	int dur(int[] t, int a, int b)
	{
		int sum = 0;
		if(a <= b){
			for(int i = a;i <= b - 1;i++){
				sum += t[i];
			}
		}else{
			for(int i = a;i < t.length;i++){
				sum += t[i];
			}
			for(int i = 0;i <= b - 1;i++){
				sum += t[i];
			}
		}
		return sum;
	}

}

500

k(<=20)個の整数a_i(i=1,...,k)を考える。これらの合計がS(<=1000)のとき、これらすべての積の最大値を求めよ。

えっこれ平均まわりだろ？と直後に思ってさくさくかいた。反例が思いつかなかったのでsubmit.

整数計画だと思う。a_iが実数だと、a_i=S/kが最適になるので、S%k個を[S/k]+1, k-(S%k)個を[S/k]として積を求めれば良い。
証明は・・一方が[S/k],[S/k]+1でないペアと、どちらも[S/k],[S/k]+1でできたペアをつくって、和が等しいときに積がどうなるかを調べると・・あとは帰納でいけるのかな。

public class MaximalProduct {

	public long maximalProduct(int s, int k) {
		int av = s / k;
		long ret = 1;
		for(int i = 0;i < s%k;i++)ret *= av+1;
		for(int i = 0;i < k-s%k;i++)ret *= av;
		return ret;
	}
}

1000

n-xyz

を最小化する整数の3つ組(x,y,z)(x<=y<=z)を求めよ。n<=1000. ただし、集合a(

<=50)にある整数(<=1000)はx,y,zに使ってはいけない。

xyz<=Mのとき、x,y,zのいずれかが必ず集合aにはいってしまうようなMの最大値を考える。aに含まれない最小の値をQとすると、x=y=z=Qのときはその制約を満たさないため、M

import java.util.BitSet;

public class AvoidingProduct {

	public int[] getTriple(int[] a, int n) {
		int N = 51*51*51;
		int min = N+1;
		int ox, oy, oz;
		ox = oy = oz = -1;
		BitSet mask = new BitSet();
		for(int q : a){
			mask.set(q);
		}
		for(int x = 1;x*x*x <= N;x++){
			if(mask.get(x))continue;
			for(int y = x;x*y*y <= N;y++){
				if(mask.get(y))continue;
				for(int z = y;x*y*z <= N;z++){
					if(mask.get(z))continue;
					int d = Math.abs(n - x*y*z);
					if(d < min){
						min = d;
						ox = x;
						oy = y;
						oz = z;
					}
				}
			}
		}
		
		return new int[]{ox, oy, oz};
	}

}