Google Code Jam 2011 Round1A

遅ればせながら，報告．

■A. FreeCell Statistics

まず，下記の2条件を満たすか調べる．
・P_G=0の時は，P_D=0でないといけない．
何故なら，P_G=0ならば，全てのゲームで負けているから．
・P_G=100の時は，P_D=100でないといけない．
理由は上とほぼ同じ．

次に，勝率がP_D[%]となる（今日の）最小のゲーム数を求める．
つまり，
P_D/100*Dが整数となるような，最小のDを求める．
つまり，
D=100/gcd(P_D,100)
である．
D≦Nならば，"Possible"．
P_Gについては，試合の勝敗を調整すれば基本的に実現可能．

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 A{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  int caze;  
16.  int t;  
17.  long n, nd, ng;  
18.   
19.  void run(){  
20.   t=sc.nextInt();  
21.   for(caze=1; caze<=t; caze++){  
22.    n=sc.nextLong();  
23.    nd=sc.nextLong();  
24.    ng=sc.nextLong();  
25.    solve();  
26.   }  
27.  }  
28.   
29.  void solve(){  
30.   long dd=100;  
31.   long dg=100;  
32.   if(ng==0&&nd>0){  
33.    answer("Broken");  
34.    return;  
35.   }  
36.   if(ng==100&&nd<100){  
37.    answer("Broken");  
38.    return;  
39.   }  
40.   long gcdD=gcd(nd, dd);  
41.   long gcdG=gcd(ng, dg);  
42.   debug(gcdD, gcdG);  
43.   nd/=gcdD;  
44.   dd/=gcdD;  
45.   ng/=gcdG;  
46.   dg/=gcdG;  
47.   debug(nd, dd, ng, dg);  
48.   long d=dd;  
49.   if(d>n){  
50.    answer("Broken");  
51.    return;  
52.   }  
53.   answer("Possible");  
54.  }  
55.   
56.  void answer(String s){  
57.   println("Case #"+caze+": "+s);  
58.  }  
59.   
60.  long gcd(long m, long n){  
61.   for(; n!=0;){  
62.    long t=m%n;  
63.    m=n;  
64.    n=t;  
65.   }  
66.   return m;  
67.  }  
68.   
69.  void println(String s){  
70.   System.out.println(s);  
71.  }  
72.   
73.  void print(String s){  
74.   System.out.print(s);  
75.  }  
76.   
77.  void debug(Object... os){  
78.   System.err.println(Arrays.deepToString(os));  
79.  }  
80.   
81.  public static void main(String[] args){  
82.   try{  
83.    System.setIn(new FileInputStream(  
84.      "D:/contest_workspace/gcj_2011_round1a/dat/A-large.in"));  
85.    System.setOut(new PrintStream(new FileOutputStream(  
86.      "D:/contest_workspace/gcj_2011_round1a/dat/A-large.out")));  
87.   }catch(Exception e){}  
88.   
89.   new A().run();  
90.   System.out.flush();  
91.   System.out.close();  
92.  }  
93. }  

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

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

public class A{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int caze;
 int t;
 long n, nd, ng;

 void run(){
  t=sc.nextInt();
  for(caze=1; caze<=t; caze++){
   n=sc.nextLong();
   nd=sc.nextLong();
   ng=sc.nextLong();
   solve();
  }
 }

 void solve(){
  long dd=100;
  long dg=100;
  if(ng==0&&nd>0){
   answer("Broken");
   return;
  }
  if(ng==100&&nd<100){
   answer("Broken");
   return;
  }
  long gcdD=gcd(nd, dd);
  long gcdG=gcd(ng, dg);
  debug(gcdD, gcdG);
  nd/=gcdD;
  dd/=gcdD;
  ng/=gcdG;
  dg/=gcdG;
  debug(nd, dd, ng, dg);
  long d=dd;
  if(d>n){
   answer("Broken");
   return;
  }
  answer("Possible");
 }

 void answer(String s){
  println("Case #"+caze+": "+s);
 }

 long gcd(long m, long n){
  for(; n!=0;){
   long t=m%n;
   m=n;
   n=t;
  }
  return m;
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  try{
   System.setIn(new FileInputStream(
     "D:/contest_workspace/gcj_2011_round1a/dat/A-large.in"));
   System.setOut(new PrintStream(new FileOutputStream(
     "D:/contest_workspace/gcj_2011_round1a/dat/A-large.out")));
  }catch(Exception e){}

  new A().run();
  System.out.flush();
  System.out.close();
 }
}

■B. The Killer Word

大雑把な方針は，DFSです．
まず，辞書単語を文字列の長さで分類します．
そして，リストの文字を順番に辞書全体に適用していきます．
その際，それぞれの辞書単語の開示状態は変わります．
この開示状態が等しいもので分類して，その集合で個々にDFSを行います．
集合の要素数が1になったら終わりです．
詳しい説明は，GCJ公式のContest Analysisを御覧下さい．
ちなみに，本番では解けませんでした．

view plainprint?

1. import java.util.*;  
2. import java.util.Map.Entry;  
3. import java.lang.*;  
4. import java.math.*;  
5. import java.io.*;  
6.   
7. import static java.lang.Math.*;  
8. import static java.util.Arrays.*;  
9.   
10. public class B{  
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int caze;  
17.  int m, n;  
18.  String[] dic, lis;  
19.  String l;  
20.   
21.  int[] bit;  
22.  int[] opend;  
23.  int[][] open;  
24.  int[] loses;  
25.   
26.  void run(){  
27.   int tt=sc.nextInt();  
28.   for(caze=1; caze<=tt; caze++){  
29.    m=sc.nextInt();  
30.    n=sc.nextInt();  
31.    dic=new String[m];  
32.    lis=new String[n];  
33.    for(int i=0; i<m; i++){  
34.     dic[i]=sc.next();  
35.    }  
36.    for(int i=0; i<n; i++){  
37.     lis[i]=sc.next();  
38.    }  
39.    solve();  
40.   }  
41.  }  
42.   
43.  void dfs(TreeSet<Integer> set, int k, int exist){  
44.   if(set.size()<=1||k>=26){  
45.    return;  
46.   }  
47.   if(((exist>>(l.charAt(k)-'a'))&1)==0){  
48.    dfs(set, k+1, exist);  
49.    return;  
50.   }  
51.   HashMap<Integer, TreeSet<Integer>> map=new HashMap<Integer, TreeSet<Integer>>();  
52.   HashMap<Integer, Integer> exists=new HashMap<Integer, Integer>();  
53.   for(int i : set){  
54.    opend[i]|=open[i][l.charAt(k)];  
55.    if(open[i][l.charAt(k)]==0){  
56.     loses[i]++;  
57.    }  
58.    if(!map.containsKey(opend[i])){  
59.     map.put(opend[i], new TreeSet<Integer>());  
60.     exists.put(opend[i], 0);  
61.    }  
62.    map.get(opend[i]).add(i);  
63.    exists.put(opend[i], exists.get(opend[i])|bit[i]);  
64.   }  
65.   for(Entry<Integer, TreeSet<Integer>> entry : map.entrySet()){  
66.    dfs(entry.getValue(), k+1, exists.get(entry.getKey()));  
67.   }  
68.  }  
69.   
70.  void solve(){  
71.   String ans="";  
72.   for(int k=0; k<n; k++){  
73.    TreeSet<Integer>[] sets=new TreeSet[10];  
74.    for(int i=0; i<10; i++){  
75.     sets[i]=new TreeSet<Integer>();  
76.    }  
77.    bit=new int[m];  
78.    opend=new int[m];  
79.    open=new int[m][256];  
80.    loses=new int[m];  
81.    int[] exists=new int[10];  
82.    for(int j=0; j<m; j++){  
83.     sets[dic[j].length()-1].add(j);  
84.     for(int i=0; i<dic[j].length(); i++){  
85.      bit[j]|=1<<(dic[j].charAt(i)-'a');  
86.      open[j][dic[j].charAt(i)]|=1<<i;  
87.      exists[dic[j].length()-1]|=1<<(dic[j].charAt(i)-'a');  
88.     }  
89.    }  
90.    l=lis[k];  
91.    for(int i=0; i<10; i++){  
92.     dfs(sets[i], 0, exists[i]);  
93.    }  
94.    int max=-1;  
95.    for(int i=0; i<m; i++){  
96.     max=max(max, loses[i]);  
97.    }  
98.    for(int i=0; i<m; i++){  
99.     if(loses[i]==max){  
100.      ans+=dic[i]+(k==n-1?"":" ");  
101.      break;  
102.     }  
103.    }  
104.   }  
105.   answer(ans);  
106.   debug(ans);  
107.  }  
108.   
109.  void answer(String s){  
110.   println("Case #"+caze+": "+s);  
111.  }  
112.   
113.  void println(String s){  
114.   System.out.println(s);  
115.  }  
116.   
117.  void print(String s){  
118.   System.out.print(s);  
119.  }  
120.   
121.  void debug(Object... os){  
122.   System.err.println(Arrays.deepToString(os));  
123.  }  
124.   
125.  public static void main(String[] args){  
126.   try{  
127.    System.setIn(new FileInputStream(  
128.      "D:/contest_workspace/gcj_2011_round1a/dat/B-large.in"));  
129.    System.setOut(new PrintStream(new FileOutputStream(  
130.      "D:/contest_workspace/gcj_2011_round1a/dat/B-large.out")));  
131.   }catch(Exception e){}  
132.   new B().run();  
133.   System.out.flush();  
134.   System.out.close();  
135.  }  
136. }  

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

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

public class B{
 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int caze;
 int m, n;
 String[] dic, lis;
 String l;

 int[] bit;
 int[] opend;
 int[][] open;
 int[] loses;

 void run(){
  int tt=sc.nextInt();
  for(caze=1; caze<=tt; caze++){
   m=sc.nextInt();
   n=sc.nextInt();
   dic=new String[m];
   lis=new String[n];
   for(int i=0; i<m; i++){
    dic[i]=sc.next();
   }
   for(int i=0; i<n; i++){
    lis[i]=sc.next();
   }
   solve();
  }
 }

 void dfs(TreeSet<Integer> set, int k, int exist){
  if(set.size()<=1||k>=26){
   return;
  }
  if(((exist>>(l.charAt(k)-'a'))&1)==0){
   dfs(set, k+1, exist);
   return;
  }
  HashMap<Integer, TreeSet<Integer>> map=new HashMap<Integer, TreeSet<Integer>>();
  HashMap<Integer, Integer> exists=new HashMap<Integer, Integer>();
  for(int i : set){
   opend[i]|=open[i][l.charAt(k)];
   if(open[i][l.charAt(k)]==0){
    loses[i]++;
   }
   if(!map.containsKey(opend[i])){
    map.put(opend[i], new TreeSet<Integer>());
    exists.put(opend[i], 0);
   }
   map.get(opend[i]).add(i);
   exists.put(opend[i], exists.get(opend[i])|bit[i]);
  }
  for(Entry<Integer, TreeSet<Integer>> entry : map.entrySet()){
   dfs(entry.getValue(), k+1, exists.get(entry.getKey()));
  }
 }

 void solve(){
  String ans="";
  for(int k=0; k<n; k++){
   TreeSet<Integer>[] sets=new TreeSet[10];
   for(int i=0; i<10; i++){
    sets[i]=new TreeSet<Integer>();
   }
   bit=new int[m];
   opend=new int[m];
   open=new int[m][256];
   loses=new int[m];
   int[] exists=new int[10];
   for(int j=0; j<m; j++){
    sets[dic[j].length()-1].add(j);
    for(int i=0; i<dic[j].length(); i++){
     bit[j]|=1<<(dic[j].charAt(i)-'a');
     open[j][dic[j].charAt(i)]|=1<<i;
     exists[dic[j].length()-1]|=1<<(dic[j].charAt(i)-'a');
    }
   }
   l=lis[k];
   for(int i=0; i<10; i++){
    dfs(sets[i], 0, exists[i]);
   }
   int max=-1;
   for(int i=0; i<m; i++){
    max=max(max, loses[i]);
   }
   for(int i=0; i<m; i++){
    if(loses[i]==max){
     ans+=dic[i]+(k==n-1?"":" ");
     break;
    }
   }
  }
  answer(ans);
  debug(ans);
 }

 void answer(String s){
  println("Case #"+caze+": "+s);
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  try{
   System.setIn(new FileInputStream(
     "D:/contest_workspace/gcj_2011_round1a/dat/B-large.in"));
   System.setOut(new PrintStream(new FileOutputStream(
     "D:/contest_workspace/gcj_2011_round1a/dat/B-large.out")));
  }catch(Exception e){}
  new B().run();
  System.out.flush();
  System.out.close();
 }
}

■Result

oo----
20pts. 870th
どうにかRound2へ進出出来ます．