TCO11 Algo Qual1

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

■Result

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

■Rating

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