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位で申し分ないと思ったけど実際そうでもない。
しかしレートは上がるらしい。