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については，試合の勝敗を調整すれば基本的に実現可能．

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を御覧下さい．
ちなみに，本番では解けませんでした．

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へ進出出来ます．