TCO11 Algo Qual1(5/15 1:00~3:00)
■MinimumLiars(Easy)
考えられる全ケースを試すだけ.import java.util.*; import java.lang.*; import java.math.*; import java.io.*; public class MinimumLiars { int INF=1<<28; double EPS=1e-9; public int getMinimum(int[] a) { int n=a.length; for(int j=0;j<=n;j++){ int s=0; for(int i=0;i<n;i++){ if(a[i]>j){ s++; } } if(j==s){ return j; } } return -1; } void debug(Object...os){ System.err.println(Arrays.deepToString(os)); } void print(String s){ System.out.print(s); } void println(String s){ System.out.println(s); } public static void main(String[] args) { // MinimumLiars temp = new MinimumLiars(); // System.out.println(temp.getMinimum(int[] claim)); } }
■FoxListeningToMusic(Medium)
O(Tn)じゃないとSystem Testで落ちます.import java.util.*; import java.lang.*; import java.math.*; import java.io.*; public class FoxListeningToMusic { int INF=1<<28; double EPS=1e-9; public double[] getProbabilities(int[] a, int t) { int n=a.length; double[] dp=new double[t+1]; dp[0]=1./n; for(int k=0;k<t;k++){ double[] d=new double[n]; for(int i=0;i<n;i++){ d[i]+=dp[k]/n; } for(int i=0;i<n;i++){ if(k+a[i]<=t){ dp[k+a[i]]+=d[i]; } } } // debug(dp); double[] res=new double[n]; for(int i=0;i<n;i++){ for(int j=t;j>t-a[i]&&j>=0;j--){ res[i]+=dp[j]; } } return res; } void debug(Object...os){ System.err.println(Arrays.deepToString(os)); } void print(String s){ System.out.print(s); } void println(String s){ System.out.println(s); } public static void main(String[] args) { } }
■Challenge Phase
Mediumにて,O(Tn2)の人を狙ったのですが,3回もミスしてしまいました.■Result
○○× +1 -3478.98pts. 332th
■Rating
1279 -> 1360600位以内なので,次のラウンドへ.Round1も残りたいですね.
0 件のコメント:
コメントを投稿