SRM 339

適当にasi1024さんとzeptometerさんと75分間でやってました

250: BusTrip
難解な英語、バスで無意味な旅行がしたいらしい、かかる時間(最小とかは無い)の計算。
探索。面倒。りんごさんも苦戦しているので良いとする。

import java.util.*;
public class BusTrip{
	public int returnTime(int a,String[]b){
		int [][]c=new int[b.length][];
		for(int i=0;i<b.length;i++){
			c[i]=new int[b[i].split(" ").length];
			for(int j=0;j<b[i].split(" ").length;j++)c[i][j]=Integer.parseInt(b[i].split(" ")[j]);
		}
		int time=0;
		int at=0;
		int shuki[]=new int[b.length];
		int val[][]=new int[b.length][];
		for(int i=0;i<b.length;i++){
			val[i]=new int[c[i].length];
			int sum=Math.abs(c[i][c[i].length-1]-c[i][0]);
			for(int j=1;j<c[i].length;j++){
				sum+=Math.abs(c[i][j]-c[i][j-1]);
			}
			for(int j=1;j<c[i].length;j++)val[i][j]=val[i][j-1]+Math.abs(c[i][j]-c[i][j-1]);
			shuki[i]=sum;
		}
	
		do{
			int t=999999999;
			int nextat=-1;
			int nexttime=-1;
			for(int i=0;i<b.length;i++){
				for(int j=0;j<c[i].length;j++){
					if(c[i][j]==at){
					int p=val[i][j]+(time-val[i][j]+shuki[i]-1)/shuki[i]*shuki[i];
					if(t>p){
						if(j+1==c[i].length){
							nextat=c[i][0];
							nexttime=Math.abs(c[i][0]-c[i][j])+p;
							t=p;
						}
						else{
							nextat=c[i][j+1];
							nexttime=Math.abs(c[i][j+1]-c[i][j])+p;
							t=p;
						}
					}}
				}
			}
			time=nexttime+1;
			at=nextat;
			System.out.println(time);
			if(time>1001)return -1;
		}while(at!=0);
		return time-1;
	}
}

450: TestBettingStrategy
どう見ても確率DP。

public class TestBettingStrategy{
	//sum,round,bet(loses)の確率DP?
	public double winProbability(int a,int b,int c,int d){
		double dp[][][]=new double[b+1][c+1][10];
		dp[a][0][0]=1;
		double prob=(double)d/100.0;
		for(int i=0;i<c;i++){
			for(int j=0;j<b;j++){
				for(int k=0;k<9;k++){
			//	System.out.println(dp[j][i][k]);
					if(j>=(1<<k)){
						dp[Math.min(b,j+(1<<k))][i+1][0]+=dp[j][i][k]*prob;
						dp[j-(1<<k)][i+1][k+1]+=dp[j][i][k]*(1-prob);
					}
				}
			}
		}
		double ret=0;
		for(int i=1;i<=c;i++)
			ret+=dp[b][i][0];
		return ret;
	}
}

1000: RPSTournament
難。二分探索?と思ったら本当に二分探索らしい。

result:
2完で454.77点。出てれば123位で申し分ないと思ったけど実際そうでもない。
しかしレートは上がるらしい。