TopCoder SRM 504.5

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

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

■TheNumbersWithLuckyLastDigit(Easy)

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

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が使えます．

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
黄色くなれるか…?!