Hatena::Grouptopcoder

tsubosakaの日記

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]);
    }
  }
}