読者です 読者をやめる 読者になる 読者になる

Google Code Jam 2009 Qualification Round

トラブルがありましたが無事終了したみたいです.

開始は日本時間で昨日の朝8時からでしたが,寝坊して8:30頃に起床して解きました.
Google側のトラブルのために入力ファイルが10:30ぐらいまで落とせずに苦労しましたが,149位でした.
(修正中で提出できなかった人がたくさんいるためあまりあてにならないが)

http://code.google.com/codejam/contest/ソースコードは全部公開されてしまってるのでここでも晒しても問題ないはず.
当方java使いのため,全部javaで解きました.

Alien Language

寝起きだったからか英語の理解に10分ぐらいかかってしまった.
ようは正規表現でマッチするかどうかをチェックすればいいのだが,
正規表現の形に置換するのでハマってしまった.
(String.replace(Char,Char)は置換した結果を返すだけで元のオブジェクトはそのまま)
なんかlargeの実行時間がやたら遅いんですけどjava正規表現なんて使うのが間違えだったかも.
スクリプト言語で書くべき問題.

import java.util.*;
public class A {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int L = sc.nextInt();
        int D = sc.nextInt();
        int N = sc.nextInt();
        String[] dictionary = new String[D];
        for(int i=0;i<D;++i)dictionary[i]=sc.next();
        for(int cases=1;cases<=N;++cases){
            int result = 0;
            String pattern = sc.next();
            pattern=pattern.replace('(','[');
            pattern=pattern.replace(')',']');
            for(int i=0;i<D;++i)if(dictionary[i].matches(pattern))result++;
            System.out.println("Case #"+cases+": "+result);
        }
    }
}

Watersheds

アルゴリズムよりも実装力を問われる問題.
各セルについてどこがsinkになるかを調べてアルファベットに直す.
時間計算量は
なので大丈夫.
(sinkの位置をちゃんとメモしながらやればだけど気にしない.)
アルファベットに直すのはTreeMapを使っているけどなので配列使っても何ら問題はない.

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

public class B {
    public static void main(String[] args) {
        new B().run();
    }
    void run() {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int cases=1;cases<=T;++cases){
            int H = sc.nextInt();
            int W = sc.nextInt();
            int[][] map = new int[H][W];
            int[][] sinkMap = new int[H][W];
            for(int i=0;i<H;++i)for(int j=0;j<W;++j)map[i][j]=sc.nextInt();
            //N W E S
            int[] dx = new int[]{ 0,-1,1,0};
            int[] dy = new int[]{-1, 0,0,1};
            for(int i=0;i<H;++i)for(int j=0;j<W;++j){
                    int ci = i, cj = j;
                    while(true){
                        int min = map[ci][cj];
                        for(int k=0;k<4;++k){
                            if(0<=ci+dy[k]&&ci+dy[k]<H&&0<=cj+dx[k]&&cj+dx[k]<W)
                                min=min(min,map[ci+dy[k]][cj+dx[k]]);
                        }
                        if(min==map[ci][cj])break;
                        for(int k=0;k<4;++k)
                            if(0<=ci+dy[k]&&ci+dy[k]<H&&0<=cj+dx[k]&&cj+dx[k]<W)
                                if(min==map[ci+dy[k]][cj+dx[k]]){
                                    ci=ci+dy[k];
                                    cj=cj+dx[k];
                                    break;
                        }                        
                    }
                    sinkMap[i][j]=ci*W+cj;
            }
            
            int[][] altitudes = new int[H][W];
            int a = 'a';
            TreeMap<Integer,Integer> tm = new TreeMap<Integer,Integer>();
            for(int i=0;i<H;++i)for(int j=0;j<W;++j){
                    if(tm.containsKey(sinkMap[i][j]))altitudes[i][j]=tm.get(sinkMap[i][j]);
                    else{
                        altitudes[i][j]=a;
                        tm.put(sinkMap[i][j],a++);
                    }
            }
            
            int result = 0;
            System.out.println("Case #"+cases+": ");
            for(int i=0;i<H;++i){
                for(int j=0;j<W;++j){
                    System.out.print((char)(altitudes[i][j])+" ");
                }
                System.out.println();
            }            
        }
       
    }
}


再帰使ってO(HW)にできました.

import static java.lang.Math.*;
import java.util.*;
public class B {
    int[] dx = new int[]{ 0,-1,1,0}, dy = new int[]{-1, 0,0,1};//N W E S
    int[][] sinkMap, map;
    int a;
    public static void main(String[] args) {
        new B().run();
    }
    void run(){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int cases=1;cases<=T;++cases){
            int H = sc.nextInt(), W = sc.nextInt();
            map = new int[H][W];
            sinkMap = new int[H][W];
            for(int i=0;i<H;++i)for(int j=0;j<W;++j)map[i][j]=sc.nextInt();
            a = 'a';
            System.out.println("Case #"+cases+": ");
            for(int i=0;i<H;++i)for(int j=0;j<W;++j)System.out.print((char)(sink(i,j,H,W))+((j<W-1)? " ":"\n"));
        }
    }
    int sink(int i, int j, int H, int W){
        if(sinkMap[i][j]!=0)return sinkMap[i][j];
        int min = map[i][j];
        for(int k=0;k<4;++k)if(0<=i+dy[k]&&i+dy[k]<H&&0<=j+dx[k]&&j+dx[k]<W)min=min(min,map[i+dy[k]][j+dx[k]]);
        if(min==map[i][j])return sinkMap[i][j]=a++;
        for(int k=0;k<4;++k)if(0<=i+dy[k]&&i+dy[k]<H&&0<=j+dx[k]&&j+dx[k]<W&&min==map[i+dy[k]][j+dx[k]])return (sinkMap[i][j]=sink(i+dy[k],j+dx[k],H,W));
        return -1;
    }
}

Welcome to Code Jam

こういう問題が一番得意です.
といいつつも,明らかにDPの問題なのに再帰で初めは書いてしまった.
smallなら再帰で解けるだろうけどlargeは無理だと入力ファイルが落とせなくて困っているうちに気づいて
サクッとDPに書き直す.

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

public class C {
    public static void main(String[] args) {
        new C().run();
    }
    void run() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.nextLine();
        for(int cases=1;cases<=N;++cases){
            String line = sc.nextLine();
            int result = solve2(line,"welcome to code jam");
            System.out.printf("Case #"+cases+": %04d\n",result);
        }
    }
    int solve(String line, String object){
        if(object.length()==0)return 1;
        int result = 0;
        for(int i=0;i<line.length();++i){
            if(line.charAt(i)==object.charAt(0))result+=solve(line.substring(i),object.substring(1));
        }
        return result%10000;
    }
    int solve2(String line, String object){
        int[] table = new int[object.length()+1];
        table[0]=1;
        for(int i=0;i<line.length();++i)for(int j=0;j<object.length();++j){
                if(line.charAt(i)==object.charAt(j))table[j+1]=(table[j+1]+table[j])%10000;
        }
        return table[object.length()];
    }
}


無駄を省くと

import java.util.*;
public class C {                                                                                                                                                          
    public static void main(String[] args) {                                                                                                                              
        Scanner sc = new Scanner(System.in);                                                                                                                              
        String object = "welcome to code jam";                                                                                                                            
        int N = sc.nextInt();sc.nextLine();                                                                                                                               
        for(int cases=1;cases<=N;++cases){                                                                                                                                
            String line = sc.nextLine();                                                                                                                                  
            int[] table = new int[object.length()+1];table[0]=1;                                                                                                          
            for(int i=0;i<line.length();++i)for(int j=0;j<object.length();++j)                                                                                            
                if(line.charAt(i)==object.charAt(j))table[j+1]=(table[j+1]+table[j])%10000;                                                                               
            System.out.printf("Case #"+cases+": %04d\n",table[object.length()]);                                                                                          
        }                                                                                                                                                                 
    }                                                                                                                                                                     
}

まとめ

2425人が満点をとり,7835人が合格点の33点を獲得してました.
次のRound1に向けて少し練習しないと.3000人通過できるのでまだ大丈夫だとは思うが..