TCO11 Algo Qual1

TCO11 Algo Qual1(5/15 1:00~3:00)

■MinimumLiars(Easy)

考えられる全ケースを試すだけ．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5. public class MinimumLiars {  
6.  int INF=1<<28;  
7.  double EPS=1e-9;  
8.   
9.  public int getMinimum(int[] a) {  
10.   int n=a.length;  
11.   for(int j=0;j<=n;j++){  
12.    int s=0;  
13.    for(int i=0;i<n;i++){  
14.     if(a[i]>j){  
15.      s++;  
16.     }  
17.    }  
18.    if(j==s){  
19.     return j;  
20.    }  
21.   }  
22.   return -1;  
23.  }  
24.   
25.  void debug(Object...os){  
26.   System.err.println(Arrays.deepToString(os));  
27.  }  
28.   
29.  void print(String s){  
30.   System.out.print(s);  
31.  }  
32.   
33.  void println(String s){  
34.   System.out.println(s);  
35.  }  
36.   
37.  public static void main(String[] args) {  
38.   // MinimumLiars temp = new MinimumLiars();  
39.   // System.out.println(temp.getMinimum(int[] claim));  
40.  }  
41. }  

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で落ちます．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5. public class FoxListeningToMusic {  
6.  int INF=1<<28;  
7.  double EPS=1e-9;  
8.   
9.  public double[] getProbabilities(int[] a, int t) {  
10.   int n=a.length;  
11.   double[] dp=new double[t+1];  
12.   dp[0]=1./n;  
13.   for(int k=0;k<t;k++){  
14.    double[] d=new double[n];  
15.    for(int i=0;i<n;i++){  
16.     d[i]+=dp[k]/n;  
17.    }  
18.    for(int i=0;i<n;i++){  
19.     if(k+a[i]<=t){  
20.      dp[k+a[i]]+=d[i];  
21.     }  
22.    }  
23.   }  
24.   // debug(dp);  
25.   double[] res=new double[n];  
26.   for(int i=0;i<n;i++){  
27.    for(int j=t;j>t-a[i]&&j>=0;j--){  
28.     res[i]+=dp[j];  
29.    }  
30.   }  
31.   return res;  
32.  }  
33.   
34.  void debug(Object...os){  
35.   System.err.println(Arrays.deepToString(os));  
36.  }  
37.   
38.  void print(String s){  
39.   System.out.print(s);  
40.  }  
41.   
42.  void println(String s){  
43.   System.out.println(s);  
44.  }  
45.   
46.  public static void main(String[] args) {  
47.  }  
48. }  

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(Tn²)の人を狙ったのですが，3回もミスしてしまいました．

■Result

○○× +1 -3
478.98pts. 332th

■Rating

1279 -> 1360
600位以内なので，次のラウンドへ．Round1も残りたいですね．