TopCoder SRM 504.5

SRM 504.5(5/18 0:00~2:00)

多忙でしたが，折角なので参加することにしました．

■TheNumbersWithLuckyLastDigit(Easy)

実際にいくつか試してみると，10で割った余りで"ほぼ"決まることが分かります．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class TheNumbersWithLuckyLastDigit {  
10.  // long INF=1L<<48;  
11.  int INF=1<<28;  
12.  double EPS=1e-9;  
13.   
14.  public int find(int n) {  
15.   int[] a={5,2,3,5,1,3,4,1,2,4};  
16.   boolean[] out=new boolean[20];  
17.   out[1]=out[2]=out[3]=out[5]=out[6]=out[9]=out[10]=out[13]=true;  
18.   if(n<20&&out[n]){  
19.    return -1;  
20.   }else{  
21.    return a[n%10];  
22.   }  
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. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class TheNumbersWithLuckyLastDigit {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public int find(int n) {
  int[] a={5,2,3,5,1,3,4,1,2,4};
  boolean[] out=new boolean[20];
  out[1]=out[2]=out[3]=out[5]=out[6]=out[9]=out[10]=out[13]=true;
  if(n<20&&out[n]){
   return -1;
  }else{
   return a[n%10];
  }
 }

 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);
 }
}

■TheJackpotDivOne(Medium)

本番ではdoubleを使っていたので，アンダーフロー(?)による精度落ちで撃墜されました． 下が修正コード．JavaならばBigIntegerが使えます．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class TheJackpotDivOne {  
10.  // long INF=1L<<48;  
11.  int INF=1<<28;  
12.  double EPS=1e-9;  
13.   
14.  public long[] find(long[] a, long m) {  
15.   int n=a.length;  
16.   for(;;){  
17.    int k=n-1;  
18.    BigInteger ave=BigInteger.ZERO;  
19.    boolean same=true;  
20.    for(int i=n-1;i>=0;i--){  
21.     if(a[i]<=a[k]){  
22.      k=i;  
23.     }  
24.     same&=a[0]==a[i];  
25.     ave=ave.add(BigInteger.valueOf(a[i]));  
26.    }  
27.    if(same){  
28.     break;  
29.    }  
30.    long x=ave.divide(BigInteger.valueOf(n)).longValue()-a[k]+1;  
31.    if(m>=x){  
32.     a[k]+=x;  
33.     m-=x;  
34.    }else{  
35.     a[k]+=m;  
36.     sort(a);  
37.     return a;  
38.    }  
39.   }  
40.   for(int i=0;i<n;i++){  
41.    a[i]+=m/n;  
42.    if(i<m%n){  
43.     a[i]++;  
44.    }  
45.   }  
46.   sort(a);  
47.   return a;  
48.  }  
49.   
50.  void debug(Object...os){  
51.   System.err.println(Arrays.deepToString(os));  
52.  }  
53.   
54.  void print(String s){  
55.   System.out.print(s);  
56.  }  
57.   
58.  void println(String s){  
59.   System.out.println(s);  
60.  }  
61. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class TheJackpotDivOne {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public long[] find(long[] a, long m) {
  int n=a.length;
  for(;;){
   int k=n-1;
   BigInteger ave=BigInteger.ZERO;
   boolean same=true;
   for(int i=n-1;i>=0;i--){
    if(a[i]<=a[k]){
     k=i;
    }
    same&=a[0]==a[i];
    ave=ave.add(BigInteger.valueOf(a[i]));
   }
   if(same){
    break;
   }
   long x=ave.divide(BigInteger.valueOf(n)).longValue()-a[k]+1;
   if(m>=x){
    a[k]+=x;
    m-=x;
   }else{
    a[k]+=m;
    sort(a);
    return a;
   }
  }
  for(int i=0;i<n;i++){
   a[i]+=m/n;
   if(i<m%n){
    a[i]++;
   }
  }
  sort(a);
  return a;
 }

 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);
 }
}

■Challenge Phase

Easyで一人撃墜．

■Result

ox- +1/-0
241.3pts. 299th
前回の教訓を生かし，1撃墜に止めました．

■Rating

1360 -> 1442
黄色くなれるか…?!