2011年5月29日日曜日

TopCoder SRM 507

SRM 507(5/29 1:00~3:00)

黄色くなれませんでした….

■TheNumbersWithLuckyLastDigit(Easy)

6~50枚の色タイルが与えられる.その中から,6枚を選び出し,立方体に貼り付ける.
どの面についても,辺で接している面とは色が異なっていなければならない.
そのようなタイルの貼り付けたは存在するか.

最初にDFSで全探索しようと思ったのが間違いでした.
実際,色ごとのタイルの枚数を調べて場合分けすれば求まるのです(もっと完結に書くことも出来ます).
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

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

 public String isPossible(String[] ss) {
  HashMap<String,Integer> map=new HashMap<String,Integer>();
  for(String s:ss){
   if(!map.containsKey(s)){
    map.put(s,0);
   }
   map.put(s,map.get(s)+1);
  }
  if(map.size()>=5){
   return "YES";
  }
  if(map.size()==4){
   int c=0;
   for(int e:map.values()){
    if(e>=2){
     c++;
    }
   }
   return c>=2?"YES":"NO";
  }
  if(map.size()==3){
   for(int e:map.values()){
    if(e<2){
     return "NO";
    }
   }
   return "YES";
  }
  return "NO";
 }
 
 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);
 }
}

■CubePacking(Medium)

1辺の長さが1の立方体Ns個と,1辺の長さがLの立方体Nb個とを詰めることが出来る直方体の最小体積を求めよ.
実は結構簡単で,3辺の内の2辺を決めると,もう1辺はすぐ求まります.
ですので,2辺を全探索しつつ,体積を算出し最小値を求めれば良いのです.
本番中は解けませんでした….
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

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

 public int getMinimumVolume(int m, int n, int len) {
  long ans=INF;
  for(long a=1;a*a*a<=INF;a++){
   for(long b=a;a*b*b<=INF;b++){
    long base=(a/len)*(b/len);
    if(base==0){
     continue;
    }
    long c=((n-1)/base+1)*len;
    long rest=m-(a*b*c-len*len*len*n);
    if(rest>0){
     c+=(rest-1)/(a*b)+1;
    }
    ans=min(ans,a*b*c);
   }
  }
  return (int)ans;
 }
 
 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

撃墜無し.SystemTestで落ちた人もRoom内には居ませんでした.

■Result

o-- +0/-0
144.37pts. 683th

■Rating

1442 -> 1365
前々回のレートに戻ってしまいました….

0 件のコメント: