TopCoder SRM 507

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

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

■TheNumbersWithLuckyLastDigit(Easy)

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

最初にDFSで全探索しようと思ったのが間違いでした．
実際，色ごとのタイルの枚数を調べて場合分けすれば求まるのです（もっと完結に書くことも出来ます）．

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 CubeStickers {  
10.  // long INF=1L<<48;  
11.  int INF=1<<28;  
12.  double EPS=1e-9;  
13.   
14.  public String isPossible(String[] ss) {  
15.   HashMap<String,Integer> map=new HashMap<String,Integer>();  
16.   for(String s:ss){  
17.    if(!map.containsKey(s)){  
18.     map.put(s,0);  
19.    }  
20.    map.put(s,map.get(s)+1);  
21.   }  
22.   if(map.size()>=5){  
23.    return "YES";  
24.   }  
25.   if(map.size()==4){  
26.    int c=0;  
27.    for(int e:map.values()){  
28.     if(e>=2){  
29.      c++;  
30.     }  
31.    }  
32.    return c>=2?"YES":"NO";  
33.   }  
34.   if(map.size()==3){  
35.    for(int e:map.values()){  
36.     if(e<2){  
37.      return "NO";  
38.     }  
39.    }  
40.    return "YES";  
41.   }  
42.   return "NO";  
43.  }  
44.    
45.  void debug(Object...os){  
46.   System.err.println(Arrays.deepToString(os));  
47.  }  
48.   
49.  void print(String s){  
50.   System.out.print(s);  
51.  }  
52.   
53.  void println(String s){  
54.   System.out.println(s);  
55.  }  
56. }  

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辺を全探索しつつ，体積を算出し最小値を求めれば良いのです．
本番中は解けませんでした…．

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 CubePacking {  
10.  long INF=1L<<32;  
11.  // int INF=1<<28;  
12.  double EPS=1e-9;  
13.   
14.  public int getMinimumVolume(int m, int n, int len) {  
15.   long ans=INF;  
16.   for(long a=1;a*a*a<=INF;a++){  
17.    for(long b=a;a*b*b<=INF;b++){  
18.     long base=(a/len)*(b/len);  
19.     if(base==0){  
20.      continue;  
21.     }  
22.     long c=((n-1)/base+1)*len;  
23.     long rest=m-(a*b*c-len*len*len*n);  
24.     if(rest>0){  
25.      c+=(rest-1)/(a*b)+1;  
26.     }  
27.     ans=min(ans,a*b*c);  
28.    }  
29.   }  
30.   return (int)ans;  
31.  }  
32.    
33.  void debug(Object...os){  
34.   System.err.println(Arrays.deepToString(os));  
35.  }  
36.   
37.  void print(String s){  
38.   System.out.print(s);  
39.  }  
40.   
41.  void println(String s){  
42.   System.out.println(s);  
43.  }  
44. }  

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
前々回のレートに戻ってしまいました…．