Hatena::Grouptopcoder

tsubosakaの日記

2009-05-13

SRM440 Div1 Medium

| 05:59

一個ルートノードを決めて、探索していったときに(あるノードの期待値) = a * (親ノードの期待値) + bと書け(ノードが葉のときはa=1.0,b=1.0、チーズのときはa=b=0.0となる)再帰的に計算するとルートノードでの期待値となる。一回の計算にノード数分に比例する時間がかかり、それをすべてのノードに対して実行するのでO(N^2)となる。

また、cafelierさんによると期待値 = 親の期待値 + 子孫の数*2 + 1となるのでこれだとチーズから始めればO(N)で計算できるけどこの式を思いつくのは難しいと思う(証明は天下り的に子供の期待値がこの形で書けているとして代入していけば帰納法で示せる。)

import java.util.*;

class Vertex{
  List<Integer> adjoint;
  Vertex(){
    adjoint = new ArrayList<Integer>();
  }
  int size(){
    return adjoint.size();
  }
  void add(int e){
    adjoint.add(e);
  }  
}

public class MazeWandering {  
  int cheeseId;
  public double expectedTime(String[] maze) {
    Vertex[] vs = createGraph(maze);
    double res = 0.0;
    for(int i = 0 ; i < vs.length ; i++){
      res += rec(vs , -1 , i)[1];
    }
    return res / vs.length;
  }
  
  double[] rec(Vertex vs[] , int parent , int cp){
    if(cp == cheeseId)
      return new double[]{0.0 , 0.0};
    Vertex v = vs[cp];
    double res[] = new double[2];
    res[0] = 0.0;
    res[1] = 1.0;    
    for(int adj : v.adjoint){
      if(adj == parent)continue;
      double a[] = rec(vs , cp , adj);
      res[0] += a[0] / v.size();
      res[1] += a[1] / v.size();
    }
    res[1] /= (1 - res[0]);
    res[0] = 1.0 / (v.size() * (1.0 - res[0]));
    return res;
  }
  
  private Vertex[] createGraph(String[] maze) {
    int W = maze[0].length();
    int H = maze.length;
    int ids[][] = new int[H][W];
    int id = 0;
    for (int i = 0; i < H; i++) {
      Arrays.fill(ids[i], -1);
      for (int j = 0; j < W; j++) {
        char c = maze[i].charAt(j);
        if(c == 'X')continue;
        if(c == '*')
          cheeseId = id;
        ids[i][j] = id++;
      }
    }
    int n = id;
    Vertex vs[] = new Vertex[n];
    int dx[] = { 1, -1, 0, 0 };
    int dy[] = { 0, 0, 1, -1 };
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        char c = maze[i].charAt(j);
        if (c == 'X') 
          continue;        
        int cid = ids[i][j];
        Vertex v = new Vertex();
        for (int k = 0; k < dx.length; k++) {
          int x = j + dx[k];
          int y = i + dy[k];
          if (x < 0 || y < 0 || x >= W || y >= H)
            continue;
          if (ids[y][x] < 0)
            continue;
          v.add(ids[y][x]);
        }
        vs[cid] = v;
      }
    }
    return vs;
  }  
}

WilliamTagWilliamTag2019/02/02 11:41i don't get cialis commercials
cialis online pagamento postepay
<a href=https://kellyannehulme.com>cheap price</a>
mail order discount cialis
does generic cialis work
https://greatwinesgrandhouses.com
buy cialis in israel
canada brand cialis sex tablets
<a href=https://kellyannehulme.com>Cialis 20 mg cheap price</a>
generic cialis online best price
cialis official site
https://kellyannehulme.com

ArnoldNizArnoldNiz2019/02/05 20:50buy cialis paypal payment
product team cialis getting ready to market case study
<a href="http://cialistlm.com">buy cialis</a>
cialis prescription limits
buy cialis black 800mg
<a href="http://xcialisxx.com">buy cialis</a>
buy cialis spain
cialis para mujeres
<a href="http://cialistlm.com">Cheap Cialis buy</a>

ArnoldNizArnoldNiz2019/02/05 21:19farmacia online cialis espana
cena cialis c20 w aptece
<a href="http://xcialisxx.com">Cheap Cialis buy</a>
cialis sale in malaysia
cialis once a day review
<a href="http://cialistlm.com">Buy Cialis Online</a>
cialis store new york
cialis daily use price
<a href="http://xcialisxx.com">buy cialis</a>