Hatena::Grouptopcoder

tsubosakaの日記

2011-03-25

GCJ Africa and Arabia 2011

| 00:14

GCJJの練習に同様のRegionalのコンテストであるGCJ Africa and Arabia 2011の問題を解いてみた。

http://code.google.com/codejam/contest/dashboard?c=842485#

問題のレベルとしてはSRMの500ぐらいの難易度かなと思った。

A. Vanishing Numbers

数字の消え方がカントール集合の構成方法そのままなので、あたえられた小数を三進小数に変換したときに1が初めに出現する桁の順で並べればよいことがわかる。

実数で計算すると精度の問題が出てくるので有理数クラスを使って計算する。

あと1が出現せず循環する場合だけど、100桁目までみて1がでてこなかったら出てこないと決め打ちで書いたら通ったw

import java.math.BigInteger;
import java.util.*;


public class A {
  static class Frac{
    BigInteger nume;
    BigInteger deno;
    Frac(BigInteger a , BigInteger b){
      nume = a;
      deno = b;
    }
    Frac sub(Frac o){
      return new Frac(nume.multiply(o.deno).subtract(deno.multiply(o.nume)) , deno.multiply(o.deno));
    }
    int comp(Frac o){
      return nume.multiply(o.deno).compareTo(deno.multiply(o.nume));
    }
  }
  //与えられた十進小数を三進小数に変換したときに1が初めに出現する位置を返す
  static int highestOneBit(String val){
    String vnume = val.substring(2);
    while(vnume.length() <= 10){
      vnume = vnume + "0";
    }
    Frac vf = new Frac(new BigInteger(vnume), BigInteger.TEN.pow(11));
    BigInteger two = new BigInteger("2");
    BigInteger three = new BigInteger("3");
    for(int i = 1 ; i <= 100 ; ++i){
      Frac divpow3 = new Frac(BigInteger.ONE , three.pow(i));
      Frac divpow32 = new Frac(two , three.pow(i));
      if(vf.comp(divpow3) >= 0){
        if(vf.comp(divpow32) > 0){
          vf = vf.sub(divpow32);          
        }else{
          return i;
        }
      }
    }
    return 101;
  }
  static class Pair implements Comparable<Pair>{
    int oneBitPos;
    double val;
    public Pair(int o , double v) {
      oneBitPos = o;
      val = v;
    }
    @Override
    public int compareTo(Pair o) {
      if(oneBitPos == o.oneBitPos){
        return Double.compare(val, o.val);
      }
      return oneBitPos - o.oneBitPos;
    }    
  }
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int cn = 1 ; cn <= T ; ++cn){
      System.out.printf("Case #%d:\n" , cn);
      int N = sc.nextInt();
      Pair ps[] = new Pair[N];
      for(int i = 0 ; i < N ; ++i){
        String s = sc.next();
        ps[i] = new Pair(highestOneBit(s), Double.parseDouble(s));
      }
      Arrays.sort(ps);
      for(int i = 0 ; i < ps.length ; ++i){
        System.out.println(ps[i].val);
      }
    }
  }
}

B. Battlefield

オイラーの定理より、エッジを付け加えたあとの頂点の次数はすべて偶数である必要がある。

グラフが連結であれば、奇点の数/2が答えとなる。

連結でないときは奇点の数が多い連結成分同士をつなぎあわせるという処理を連結成分がひとつになるまで繰り返す。

import java.util.*;

public class B {
  static int dfs(int cp , boolean vis[] , int degree[] , boolean adj[][]){
    if(vis[cp])return 0;
    vis[cp] = true;
    int ret = degree[cp] % 2 == 0 ? 0 : 1;
    for(int i = 0 ; i < vis.length ; ++i){
      if(!adj[cp][i])continue;
      ret += dfs(i , vis , degree , adj);
    }
    return ret;
  }
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int cn = 1 ; cn <= T ; ++cn){
      int N = sc.nextInt();
      int R = sc.nextInt();
      int degree[] = new int[N];
      boolean adj[][] = new boolean[N][N];              
      for(int i = 0 ; i < R ; ++i){
        int s = sc.nextInt();
        int t = sc.nextInt();
        degree[s]++;
        degree[t]++;
        adj[s][t] = adj[t][s] = true;
      }
      PriorityQueue<Integer> odds = new PriorityQueue<Integer>(10 , new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
          return o2 - o1;
        }
      });
      boolean vis[] = new boolean[N];
      for(int i = 0 ; i < N ; ++i){
        if(degree[i] == 0 || vis[i])continue;
        odds.add(dfs(i, vis, degree, adj));
      }
      int ret = 0;
      while(odds.size() > 1){
        int o0 = odds.poll();
        int o1 = odds.poll();
        if(o0 > 0 && o1 > 0){
          odds.add(o0 + o1 - 2);
        }else if(o0 == 0){
          odds.add(2);
        }else if(o1 == 0){
          odds.add(o0);
        }
        ++ret;
      }
      ret += odds.poll() / 2;
      System.out.printf("Case #%d: %d\n" , cn , ret);
    }
  }
}

C. Radio Receiver

ラジオの受信距離Dに関して二分探索.

Dを固定して、イベントを起きる時刻が早い順に処理していく。一つ前のイベントまでをすべて受信できる数直線上の位置の範囲を(left,right)とすると現在のイベントeを処理可能な範囲は(left - t , right + t)と(e.pos - D , e.pos + D)のintersectionとなる。(ここでtは現在のイベントと一つ前のイベントの間の時間)

import java.util.*;
public class C {
  static class Event implements Comparable<Event> {
    int pos;
    int time;
    Event(int p, int t) {
      pos = p;
      time = t;
    }
    @Override
    public int compareTo(Event o) {
      return time - o.time;
    }
  }

  static boolean can(double D, Event es[]) {
    double left = es[0].pos - D;
    double right = es[0].pos + D;
    for (int i = 1; i < es.length; ++i) {
      Event e = es[i];
      double t = e.time - es[i - 1].time;
      // intersect (left - t , right + t) and (e.pos - D , e.pos + D)
      left = Math.max(left - t, e.pos - D);
      right = Math.min(right + t, e.pos + D);
      if (left > right)
        return false;
    }
    return true;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int C = sc.nextInt();
    for (int cn = 1; cn <= C; ++cn) {
      int N = sc.nextInt();
      Event es[] = new Event[N];
      for (int n = 0; n < N; ++n) {
        int p = sc.nextInt();
        int t = sc.nextInt();
        es[n] = new Event(p, t);
      }
      Arrays.sort(es);
      double low = 0.0;
      double high = 1.0E9;
      for (int rep = 0; rep < 100; ++rep) {
        double D = (low + high) * 0.5;
        if (can(D, es)) {
          high = D;
        } else {
          low = D;
        }
      }
      System.out.printf("Case #%d: %.9f\n", cn, low);
    }
  }
}

2009-09-27

Google Code Jam Round 2

| 18:42

1189位で敗退。解いたのはA,C,Dのsmallでした

A-small

とりあえずサイズが8なのでBFSした。

A-Largeの解放が思いつかなかったので他に

C-small

最初なぜかグラフを書いて、連結成分の個数を求めるだけどか思って実装したけどサンプルにも合わなかったのでDへ

D-small

サイズが3なので2つ以下の時は1つの円に1つのスプリンクラーを使えばよい、3つのときは1つの円にまず1つ使っておいて、残り2つの円を覆う最小の半径を計算すればよい。

最初、円に触れればいいと勘違いをして、コードを書いていてサンプルを通して気づいて、3つのときは直したのだけど2つ以下の時をなおし忘れてWAを1度もらった。

C-small

使える部分集合を列挙して、最小の個数の部分集合で全部を被うようなものを見つけるという方針で書く。これだと f(S) = min_{A} (f(S / A)) (Aは重なりが起きないチャートの集合)で計算してやればよい。最悪(2^16)^2かかるけど4分あれば間に合うと思って入力を食わせたら6分かかった。最適化をするのが面倒だったので、入力のうち引数で与えられた範囲内のケース番号を実行するというようにコードを書き換えてコンソールを3つ立ち上げて並列実行させたら通った。


この時点でB全部かC or DのLargeを解かないと500位に入るのは難しかったのだが、なぜかAのLargeを考えるとかをしてしまう。途中で気づいてCとDを考えたけど時間内には間に合わず。

2009-09-12

Google Code Jam Round 1A

| 13:08

A-small

cafelierさんの日記より引用

『"各桁の数字を二乗して総和を取る"という演算を繰り返して1になれる自然数をhappy numberという。baseによって違うので2進表記ではhappyでも10進だと違ったりする。入力で与えられる全てのbaseでhappyになるような最小の数を答えよう』

http://topcoder.g.hatena.ne.jp/cafelier/20090912/1252727099
  • とりあえず2から順番に探していって出力するコードを書いてみる。
  • 一応サンプルに対しては正しく通った
  • ここで2,3,4...10とかやると当然結果が返ってこない
  • で結果をキャッシュするとか始めるが遅い
  • そういえば2桁のときは全部通っているのだからとりあえずsmallは通しておくべきと思って通す。

よくわからなくなったのでBは問題が長かったのでCへ

C

http://en.wikipedia.org/wiki/Coupon_collector%27s_problem|title]の複数セット買えるバージョン

とりあえず全部で4枚あって、一度に2枚買える場合を考えてみる。

f:id:tsubosaka:20090912131415j:image

みたいな図が書ける。

まずあるノードiに待機する期待時間は 1 / (1 - p_{ii}) (ここでp_{ij}はノードiからノードjに行く確率)で計算できる。

ここでノード2からノード2にとどまる時間は1.2でその後ノード2->4に行く確率が1/6/(1 - 1/6) = 1/5でノード2->3に行く確率は4/5である。

次にノード3についたというときの条件付き期待値は1.0 + 1.2 = 2.2でとどまる期待時間は2.0である。その後ノード3->4に行く確率は1である。

最後にノード4についた時の条件付き期待確率は (ノード2から来た場合の期待値) + (ノード4から来た場合の期待値)なので2.2 * 1/5 + 4.2 * 4 / 5 = 3.8である。

  • 以上のことをコードに落とすだけなのだが、条件付き確率とか期待値とかひさびさにやったのでかなり混乱する。

A-large

  • そういえば999999999でbaseが10のときでも810ぐらいにしかならない。たぶん答えはintに収まるからせいぜい1から9999までに対してその数字がhappy numberかどうかを持っておけば一回の変換で4桁以下になるので、その値を用いてhappya numberかどうかを判定する
  • 4桁とかintに収まるとかは確証はなかったけど,2..10に対してテストすると11814485と10秒ぐらいで返ってきたので500ケースすべてそれだと間に合わないがそういうことはないと思いlargeをダウンロード
  • だいたい1分弱で終わったのでサブミット
package r1a;

import java.util.*;


public class A {
  static int next(int x , int base){
    int res = 0;
    while(x != 0){
      int rem = x % base;
      res += rem * rem;
      x /= base;
    }
    return res;
  }
  
  static boolean ishappy(int k , int base){
    int cur = k;
    Set<Integer> visit = new HashSet<Integer>();
    visit.add(cur);
    while(cur != 1){
      cur = next(cur , base);
      if(visit.contains(cur)){
        return false;
      }
      visit.add(cur);
    }
    return true;
  }

  public static void main(String[] args) {
    boolean memo[][] = new boolean[11][10001];
    for(int i = 2 ; i <= 10 ; i++){
      for(int j = 1 ; j <= 10000 ; j++){
        if(ishappy(j, i)){
          memo[i][j] = true;
        }
      }
    }    
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    sc.nextLine();
    for(int t = 1 ; t <= T ; t++){
      String line = sc.nextLine();
      String arr[] = line.split("\\s+");
      int bases[] = new int[arr.length];
      for(int i = 0 ; i < arr.length ; i++){
        bases[i] = Integer.parseInt(arr[i]);
      }      
      loop: for(int k = 2 ; ; k++){
        for(int base : bases){
          int next = next(k , base);
          if(!memo[base][next])
            continue loop;
        }
        System.out.printf("Case #%d: %d\n",t , k);
        break;
      }
    }
  }
}
  • C
package r1a;

import java.util.*;

public class C {
  public static void main(String[] args) {
    long comb[][] = new long[41][41];
    comb[0][0] = 1;
    for(int n = 1 ; n < comb.length ; n++){
      comb[n][0] = 1;
      for(int m = 1 ; m < comb.length ; m++){
        comb[n][m] = comb[n - 1][m] + comb[n - 1][m - 1];
      }
    }    
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int t = 1 ; t <= T ; t++){
      int C = sc.nextInt();
      int N = sc.nextInt();
      double probs[] = new double[C + 1];
      probs[0] = 1.0;
      probs[N] = 1.0;
      for(int e = 1 ; e < C ; e++){
        if(e < N)continue;
        double same = comb[e][N] * 1.0 / comb[C][N];
        double other = (1.0 - same);
        for(int x = 1 ; x <= N ; x++){
          if(e + x > C)continue;
          double prob = (comb[C - e][x] * 1.0 / comb[C][N]) * comb[e][N - x];
          prob /= other;
          probs[e + x] += probs[e] * prob;
        }
      }
      double exp[] = new double[C + 1];
      exp[0] = 0.0;
      exp[N] = 1.0;
      for(int e = 1 ; e < C ; e++){
        if(e < N)continue;
        double same = comb[e][N] * 1.0 / comb[C][N];
        double other = (1.0 - same);
        double wtime = 1.0 / (1.0 - same);
        double et = exp[e];
        double net = (et + wtime);
        for(int x = 1 ; x <= N ; x++){
          if(e + x > C)continue;
          double prob = (comb[C - e][x] * 1.0 / comb[C][N]) * comb[e][N - x];
          prob /= other;
          exp[e + x] += net * prob * (probs[e] / probs[e + x]);
        }
      }
      System.out.printf("Case #%d: %.10f\n" , t , exp[C]);
    }
  }
}

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:試合後(を[に置換すればまんま正規表現ということがわかってへこむ