Hatena::Grouptopcoder

tsubosakaの日記

2009-09-04

Google Code Jam Qualification Round 2009

| 21:51

1年ぶりのCode Jamtwitterのログをみると3問解くのに1:12かかっている。

上位25位は無理なので、目標としては去年のオンサイトと同じであるRound 3の500位までに入りたい*1。ただ3000人->500人なので結構運の要素が絡んできそうな気はする。

A

正規表現っぽい*2文字列が与えられるのでパターンに一致する文字列の数を求めよという問題。

)でsplitとかわけのわからないことを試みたせいで1WA。その後まじめにパースを行って通す。

B

点Aから点Bに水が流れるとき、点Aと点Bは同じグループに属するということが分かる。すべての点に対して自分とその流れ先のグループを併合するという作業を行って、各グループに左上から'a'-'z'を割り当てていけばよい。

グループの併合はUnionFindを用いればよい。

C


DP


package qround;

import java.util.Scanner;

class Matcher{
  int length;
  boolean accept[][];
  Matcher(String pattern , int L){
    length = L;
    accept = new boolean[L][26];
    init(pattern);
  }

  private void init(String pattern) {
    int ai = 0;
    int i = 0;
    while(ai < length){
      char c = pattern.charAt(i++);
      if(c == '('){
        while(true){
          c = pattern.charAt(i++);
          if(c == ')'){
            ++ai;
            break;
          }else{
            accept[ai][c - 'a'] = true;
          }
        }
      }else{
        accept[ai++][c - 'a'] = true;
      }
    }
  }
  
  boolean match(String word){
    for(int i = 0 ; i < length ; ++i){
      int ci = word.charAt(i) - 'a';
      if(!accept[i][ci]){
        return false;
      }
    }
    return true;
  }
}
public class A {
  public static void main(String[] args) throws Exception{
    Scanner sc = new Scanner(System.in);
    int L = sc.nextInt();
    int D = sc.nextInt();
    int N = sc.nextInt();
    String words[] = new String[D];
    for(int i = 0 ; i < words.length ; ++i){
      words[i] = sc.next();
    }
    for(int cn = 1 ; cn <= N ; ++cn){
      String pattern = sc.next();
      Matcher m = new Matcher(pattern , L);
      int res = 0;
      for(String word : words){
        if(m.match(word)){
          ++res;
        }
      }
      System.out.printf("Case #%d: %d\n" , cn , res);
    }
  }
}
package qround;

import java.util.HashMap;

import java.util.Map;
import java.util.Scanner;

class UnionFind {
  private int p[];
  private int rank[];

  public UnionFind(int n) {

    p = new int[n];
    for (int i = 0; i < n; i++)
      p[i] = i;
    rank = new int[n];
  }

  public void union(int x, int y) {
    link(find(x), find(y));
  }

  private void link(int x, int y) {
    if (x == y)
      return;
    if (rank[x] > rank[y]) {
      p[y] = x;
    } else {
      p[x] = y;
      if (rank[x] == rank[y]) {
        rank[y]++;
      }
    }
  }

  public int find(int x) {
    if (x != p[x]) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

public class B {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    for(int cn = 1 ; cn <= N ; cn++){
      System.out.printf("Case #%d:\n" , cn);
      int H = sc.nextInt();
      int W = sc.nextInt();
      int cells[][] = new int[H][W];
      for(int i = 0 ; i < H ; i++){
        for(int j = 0 ; j < W ; j++){
          cells[i][j] = sc.nextInt();
        }
      }
      UnionFind uf = new UnionFind(H * W);
      int dy[] = { -1 , 0 , 0 , 1};
      int dx[] = {  0 ,-1 , 1 , 0};
      for(int h = 0 ; h < H ; h++){
        for(int w = 0 ; w < W ; w++){
          int cp = h * W + w;
          int minp = -1;
          int mh = Integer.MAX_VALUE;
          for(int k = 0 ; k < 4 ; k++){
            int nh = h + dy[k];
            int nw = w + dx[k];
            if(nh < 0 || nw < 0 || nh >= H || nw >= W)continue;
            int np = nh * W + nw;
            if(cells[nh][nw] < mh && cells[nh][nw] < cells[h][w]){
              mh = cells[nh][nw];
              minp = np;
            }
          }
          if(minp >= 0){
            uf.union(cp, minp);
          }
        }
      }
      Map<Integer, Character> map = new HashMap<Integer, Character>();
      int ci = 0;
      for(int h = 0 ; h < H ; h++){
        for(int w = 0 ; w < W ; w++){
          int f = uf.find(h * W + w);
          if(!map.containsKey(f)){
            map.put(f, (char)(ci + 'a'));
            ci++;
          }
          char c = map.get(f);
          System.out.print(c+" ");
        }
        System.out.println();
      }
    }
  }
}
package qround;

import java.util.Scanner;

public class C {
  final static int MOD = 10000;
  static int solve(String input){
    String target = "welcome to code jam";
    int dp[][] = new int[input.length() + 1][target.length() + 1];
    dp[0][0] = 1;
    for(int i = 1 ; i <= input.length() ; i++){
      dp[i][0] = (dp[i][0] + dp[i - 1][0]) % MOD;
      for(int j = 0 ; j < target.length() ; j++){
        if(input.charAt(i - 1) == target.charAt(j)){
          dp[i][j + 1] = (dp[i][j + 1] + dp[i - 1][j + 1] + dp[i - 1][j]) % MOD;          
        }else{
          dp[i][j + 1] = (dp[i][j + 1] + dp[i - 1][j + 1]) % MOD;          
        }
      }
    }
    return dp[input.length()][target.length()];
  }
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    sc.nextLine();
    for(int cn = 1 ; cn <= N ; cn++){
      String line = sc.nextLine();
      int res = solve(line);
      System.out.printf("Case #%d: %04d\n" , cn , res);
    }
  }
}

*1:Tシャツももらえるし

*2:試合後(を[に置換すればまんま正規表現ということがわかってへこむ