Hatena::Grouptopcoder

tsubosakaの日記

2010-07-18

SRM 476

12:17

○ ○ ×で46位。1807->1942

250

Badgerをk匹購入するかを全探索する。

Badgerを買う数kを固定した時、各Badgerへの餌の量はhunger + (k - 1) * greedyで決定するので、餌の量の少ない順で購入すればよい。


public class Badgers {
  boolean can(int hunger[] , int greed[] , int totalFood , int k){
    int N = hunger.length;
    int cost[] = new int[N];
    for(int i = 0 ; i < N ; ++i)
      cost[i] = hunger[i] + (k - 1) * greed[i];    
    Arrays.sort(cost);
    int tot = 0;
    for(int i = 0 ; i < k ; ++i)
      tot += cost[i];    
    return tot <= totalFood;
  }
  
  public int feedMost(int[] hunger, int[] greed, int totalFood) {
    int N = hunger.length;
    for(int i = N ; i >= 1 ; --i){
      if(can(hunger , greed , totalFood , i)){
        return i;
      }
    }
    return 0;
  }
}

500

最初、36*36の隣接行列でハミルトン路を見つけろという問題だと思い、計算量的に無理じゃねえと思う。

よく問題を読むと、入力の隣接リストは36文字以下のスペース区切りの文字列で与えられる+node 1から接続されていないノードはたどらなくてもよいので16ノードのハミルトン路を求めればよいということになる。

これならO(2^16 16^2)で求まるので解ける。*1

状態としては(すでに訪れたノードの集合) * (現在のノード位置)を使ってメモ化再帰することになる。

再帰式は

 p(v,c) = \sum_{a \in A(c)} select(a) * p(v + \{a\} , a)

となる。

ここでselect(a)はノードaが画面に表示されかつそのノードを選んだ時に巡回できる確率が一番大きくなっている場合の確率である。現在の状態から行けるノードに関する確率値を計算してソートしたときに、k番目に小さい値がトップになる場合の数はcomb(k-1,K-1)となり、すべての場合の数がcomb(|A(c)|,K)となることからこの値は容易に計算できる。

public class FriendTour {
  double comb[][];
  double memo[][];
  int friends[][];
  int map[];
  int K;
  double rec(int pos , int visit){
    if(memo[pos][visit] >= 0)return memo[pos][visit];    
    if(visit == memo[0].length - 1)return 1.0;    
    int L = friends[pos].length;
    double probs[] = new double[L];
    for(int i = 0 ; i < L ; ++i){
      int adj = friends[pos][i];
      int m = map[adj];
      if(map[adj] >= 0 && (visit & (1 << m)) == 0){
        probs[i] = rec(adj , visit | 1 << m);
      }
    }
    Arrays.sort(probs);
    double ret = 0;
    if(K >= L){
      ret = probs[L - 1];
    }else{
      for(int i = K - 1 ; i < probs.length ; ++i){
        ret += (comb[i][K - 1] / comb[L][K]) * probs[i] ;
      }
    }
    return memo[pos][visit] = ret;
  }
  
  void initCombination(){
    comb = new double[40][40];
    comb[0][0] = 1;
    for(int n = 1 ; n < comb.length ; ++n){
      comb[n][0] = comb[n][n] = 1;
      for(int k = 1 ; k < n ; ++k){
        comb[n][k] = comb[n - 1][k - 1] + comb[n - 1][k];
      }
    }
  }
  
  public double tourProbability(String[] friends, int K) {
    int N = friends.length;
    int flist[][] = new int[N][];
    for(int i = 0 ; i < N ; ++i){
      String arr[] = friends[i].split("\\s+");
      flist[i] = new int[arr.length];
      for(int j = 0 ; j < arr.length ; ++j){
        flist[i][j] = Integer.parseInt(arr[j]) - 1;
      }
    }
    int fn = flist[0].length;
    int map[] = new int[N];
    Arrays.fill(map, -1);
    map[0] = 0;
    for(int i = 0 ; i < fn ; ++i){
      map[flist[0][i]] = i + 1;
    }
    initCombination();
    memo = new double[N][1 << (fn + 1)];
    for(int i = 0 ; i < N ; ++i){
      Arrays.fill(memo[i], -1);
    }
    this.friends = flist;
    this.K = K;
    this.map = map;
    return rec(0 , 1);
  }
}

*1:本番ではO(2^16 16^3)の解を出したので非常にぎりぎりでした

DoraDora2011/08/30 13:27I went to tons of links boefre this, what was I thinking?

htlnsookhrihtlnsookhri2011/09/01 17:01wvR5R2 , [url=http://eadnstovylin.com/]eadnstovylin[/url], [link=http://wdpzgpxmnpbe.com/]wdpzgpxmnpbe[/link], http://bcxwdcbhwrgu.com/

cecvholcecvhol2011/09/03 17:27Aor0j8 <a href="http://qhachbnqbpsn.com/">qhachbnqbpsn</a>

clqsbtibclqsbtib2011/09/04 01:25ZWCsSK , [url=http://acarwqyzrfvi.com/]acarwqyzrfvi[/url], [link=http://zfyfxhwziech.com/]zfyfxhwziech[/link], http://arvudbqaoktd.com/