SRM459 Div2

TopCoderのSRMに初参加した。Emacsで編集できるようにしておいたのが良かった。 250と1000は通ったが、500はSystemTestで失敗した。無駄が多いコードを書いているので、今後他の人の洗練されたコードを見て勉強するつもりだ。

250

RecursiveっていってるのでRecursiveに解いた。精度が心配だったがどうにかなった。今度からMath.PIを使う。

500

スパゲッティコード。ソートの必要のないところでソートしたり、最後のループがややこしかったり。
当然陥落した。

1000

ワニ池とか怖い＞＜
シミュレートして解いた。

コードたち

250コード

public class RecursiveFigures{
    public double getArea(int sideLength, int K){
	return getAreaSub((double)sideLength, K);
    }

    public static double getAreaSub(double sideLength, int K){
	double pi = 3.14159265358979323846;
	if(K == 1)
	    return sideLength * sideLength * pi / 4;
	else
	    return sideLength * sideLength * pi / 4 - sideLength * sideLength / 2 + getAreaSub(sideLength / Math.sqrt(2), K - 1);
    }
}

500コード

public class Inequalities{
    public int maximumSubset(String[] inequalities){
	int[] types = new int[inequalities.length];
	int[] cs = new int[inequalities.length];
	//
	for(int i=0; i < inequalities.length; i++){
	    int type=0;
	    if(inequalities[i].split(" ")[1].equals("<")){
		type = 1;
	    }else
	    if(inequalities[i].split(" ")[1].equals("<=")){
		type = 2;
	    }else
	    if(inequalities[i].split(" ")[1].equals("=")){
		type = 3;
	    }else
	    if(inequalities[i].split(" ")[1].equals(">")){
		type = 4;
	    }else
	    if(inequalities[i].split(" ")[1].equals(">=")){
		type = 5;
	    }
	    types[i] = type;
	    cs[i] = Integer.parseInt(inequalities[i].split(" ")[2]);
	}
	//

	Integer[] seps = new Integer[inequalities.length];
	for(int i=0; i < inequalities.length; i++){
	    seps[i] = Integer.valueOf(cs[i]);
	}
	Arrays.sort(seps);

	int[] iseps = new int[inequalities.length];
	for(int i=0; i < inequalities.length; i++){
	    iseps[i] = seps[i].intValue();
	}

	int max = 0;
	for(int i=0; i < inequalities.length; i++){
	    int count = 0;
	    for(double j=(double)iseps[i]; count < 3 && i < inequalities.length - 1; j += 0.1){
		count++;
		int ineqlsmet = 0;
		for(int k=0; k < inequalities.length; k++){
		    if(types[k] == 1){
			if(j < (double)cs[k])
			    ineqlsmet++;
		    }else
		    if(types[k] == 2){
			if(j <= (double)cs[k])
			    ineqlsmet++;
		    }else
		    if(types[k] == 3){
			if(j == (double)cs[k])
			    ineqlsmet++;
		    }else
		    if(types[k] == 4){
			if(j > (double)cs[k])
			    ineqlsmet++;
		    }else
		    if(types[k] == 5){
			if(j >= (double)cs[k])
			    ineqlsmet++;
		    }
		}
		if(max < ineqlsmet){
		    //System.out.println(j);
		    max = ineqlsmet;
		}
		if(count == 1)
		    j -= 0.3;
	    }
	}
	return max;
    }
}

1000コード

public class ParkAmusement{
    public double getProbability(String[] landings, int startLanding, int K){
	int len = landings.length;
	double[] p = new double[len];
	double[] fp = new double[len];
	boolean[][] adj = new boolean[len][len];
	boolean[] goalp = new boolean[len];
	boolean[] pondp = new boolean[len];
	int[] npipes = new int[len];
	int fc = 0;
	for(int i=0; i < len; i++){
	    for(int j=0; j < len; j++){
		adj[i][j] = false;
	    }
	}
	for(int i=0; i < len; i++){
	    npipes[i] = 0;
	    if(landings[i].charAt(i) == 'E'){
		goalp[i] = true;
		pondp[i] = false;
	    }else if(landings[i].charAt(i) == 'P'){
		goalp[i] = false;
		pondp[i] = true;
	    }else{
		goalp[i] = false;
		pondp[i] = false;
		fc++;
		for(int j=0; j < len; j++){
		    if(landings[i].charAt(j) == '1'){
			adj[i][j] = true;
			npipes[i]++;
		    }
		}
	    }
	}
	//
	for(int i=0; i < len; i++){
	    if(!goalp[i] && !pondp[i]){
		p[i] = 1.0 / (double)fc;
	    }
	}
	fp[startLanding] = 1.0 / (double)fc;
	double ep = 0;
	double fep = 0;
	//
	for(int i=0; i < K; i++){
	    double[] np = new double[len];
	    double[] nfp = new double[len];
	    for(int j=0; j < len; j++){
		np[j] = 0.0;
		nfp[j] = 0.0;
	    }

	    for(int j=0; j < len; j++){
		if(!goalp[j] && !pondp[j]){
		    for(int k=0; k < len; k++){
			if( j == k){
			    continue;
			}else if(goalp[k] && adj[j][k]){
			    if( i == K-1 ){
				ep += p[j] / (double)npipes[j];
				fep += fp[j] / (double)npipes[j];
			    }
			}else{
			    if(adj[j][k]){
				np[k] += p[j] / (double)npipes[j];
				nfp[k] += fp[j] / (double)npipes[j];
			    }
			}
		    }
		}
	    }

	    p = np;
	    fp = nfp;
	}

	return fep / ep;
    }
}