SRM365

Rate 1614->1664
何か点数にだまされた気がする．

300

n^2の約数の中でmod 4をとったときに1となるものの個数と3となるものの個数を求めよという問題．nは10^9ぐらいまで．
まず，nの約数をO(n^(1/2))で列挙する．約数の数はそんなには大きくならないので約数同士で積をとればn^2の約数を列挙できる．
ただ，思いつくのに時間がかかりすぎた．

500

数字のリストが与えられたときに，部分等差数列でリストの中の数を割合的に最も大きく含むものを求めよという問題．
例えばリストが{1,3,5,8}の時，部分列が{1,3,5,7}ならば3/4．{1,2,3,4,5,6,7,8}ならば3/8という風になる．ただし部分列は少なくとも3つのリストの中の数を含み，端を一つ伸ばしたときに({1,3,5,7}なら{-1,1,3,5,7,9})リストの区間を覆う必要がある．

リストから数字を3つ選んでそれを通るような等差数列を全部列挙して割合を求めて比較すればよくてそれだとO(n^4)なのでnが50までなので解ける．

ただ自分は勘違いしていてリストの中の数字の長さが18以下というのをリストの要素数が18以下と思いこんで18 * (2^18)なら普通に間に合うと思ったら落とされた．

1000

読んでる暇がなかったんだけど，こっちの方が500より解いている人が多くて問題を読んでみるとグラフが与えられた時にu -> vという枝が存在すればuのラベル番号がvのラベル番号よりも小さくなるというラベルづけをしろという問題．
トポロジカルソート

とりあえず直した500のコードとついでに300のコードを貼っておく．

300

import java.util.*;
public class PointsOnCircle {
    public long count(int r) {
    	Set<Long> divisorN = new HashSet<Long>();
    	int sr = (int)Math.sqrt(r) + 1;
    	sr = Math.min(sr, r);
    	for(long j = 1 ; j <= sr ; j++){
    		if(r % j ==0){
    			divisorN.add(j);
    			divisorN.add(r/j);
    		}
    	}
    	Set<Long> divisorN2 = new HashSet<Long>();
    	for(long d1:divisorN)
    		for(long d2:divisorN)
    			divisorN2.add(d1 * d2);
    	long dmod[] = new long[4];
    	for(long l:divisorN2)
    		dmod[(int)(l%4)]++;    	
    	return 4L * (dmod[1] - dmod[3]);
    }
}

500

public class ArithmeticProgressions {
	private String[] calc(BigInteger[] numbers){
		Arrays.sort(numbers);
		if(numbers.length <= 2){
			return new String[]{"0" , "1"};
		}
		BigInteger m = numbers[0];
		BigInteger M = numbers[0];
		for(BigInteger b : numbers){
			m = b.min(m);
			M = b.max(M);
		}
		List<Frac> fracs = new ArrayList<Frac>();
		for(int i = 0; i < numbers.length;i++){
			for(int j = i+1;j < numbers.length;j++ ){
				for(int k = j+1 ; k < numbers.length; k++){
					BigInteger d1 = numbers[j].subtract(numbers[i]);
					BigInteger d2 = numbers[k].subtract(numbers[j]);
					BigInteger d = d1.gcd(d2);				
					BigInteger first = numbers[i];
					int count = 0;
					for(BigInteger b : numbers){
						BigInteger diff = (first.subtract(b)).abs();
						if((diff.mod(d)).equals(BigInteger.ZERO)){
							count++;
						}
					}
					BigInteger b = first.subtract(m).divide(d);
					b = b.add( ( M.subtract(first) ).divide(d));
					b = b.add(BigInteger.ONE);
					Frac f = new Frac(BigInteger.valueOf(count),b);
					fracs.add(f);
				}
			}
		}
		Collections.sort(fracs);
		Frac res = fracs.get(0);
		return new String[]{res.a.toString(),res.b.toString()};
	}
	class Frac implements Comparable<Frac>{
		BigInteger a;
		BigInteger b;
		void init(){
			BigInteger gcd = a.gcd(b);
			a = a.divide(gcd);
			b = b.divide(gcd);			
		}
		Frac(BigInteger a,BigInteger b){
			this.a = a;
			this.b = b;
			init();
		}
		public int compareTo(Frac f) {
			BigInteger l = a.multiply(f.b);
			BigInteger r = b.multiply(f.a);
			return -l.compareTo(r);
		}
	}
    public String[] maxAptitude(String[] numbers) {
    	BigInteger bNumbers[] = new BigInteger[numbers.length];
    	for(int i = 0;i < numbers.length;i++){
    		bNumbers[i] = new BigInteger(numbers[i]);
    	}
        return calc(bNumbers);
    }
}