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/-0144.37pts. 683th
■Rating
1442 -> 1365前々回のレートに戻ってしまいました….
0 件のコメント:
コメントを投稿