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

2009-04-20

SRM 439 Div1 Medium

| 20:08

言われるとなるほどと思うのだが本番ではなかなか思いつかない。

まず、$の数が1つのときは A B B B ... という周期的な列になるため容易に求まる。また$の数が2つ以上のときは変数の長さが常に2倍以上になるため、s <= 32のときのみを考えればよい。

import java.util.*;
public class EndlessStringMachine {
  int cnt(String s) {
    int cnt = 0;
    for (char c : s.toCharArray())
      if (c == '$')cnt++;
    return cnt;
  }
  char rec(String in , String p , int s , int i , List<Long> ls){
    if(s == 0)return in.charAt(i);
    long plen = ls.get(s - 1);
    for(char c : p.toCharArray())
      if(c == '$')
        if(i < plen)return rec(in, p, s - 1, i, ls);
        else i -= plen;
      else if(i-- == 0)return c;
    return '-';
  }
  public String getFragment(String in, String p, int s, int L, int R) {
    L--; R--;
    long dn = cnt(p);
    StringBuilder sb = new StringBuilder();
    if (dn == 1) {
      int plen = p.length() - 1;
      long tlen = in.length() + plen * (long)s;
      for (int i = L; i <= R; i++)
        if (i < in.length())sb.append(in.charAt(i));
        else if(i >= tlen)sb.append('-');
        else sb.append( p.charAt(1 + (i - in.length()) % plen));      
    } else {
      List<Long> ls = new ArrayList<Long>();
      ls.add((long)in.length());
      for (int i = 1; i <= s; i++) {
        long li = (ls.get(i - 1) * dn) + (p.length() - dn);
        ls.add(li);
        if (li >= R)break;
      }
      for(int index = L ; index <= R ; index++)
        sb.append(rec(in, p, ls.size() - 1 , index, ls));      
    }
    return sb.toString();
  }
}

2009-01-15

SRM 286 Div1 Medium

| 09:33

常にプレイヤー0から始めるとすれば各プレイヤーの勝利数は(green,red,black)の値で一意に定まる.残りの色の数を状態としてメモ付き探索.

public class BallGift {
  long memo[][][][];
  int players;
  long[] rec(int green , int red , int black, int pnum){
    if(memo[green][red][black] != null){
      return memo[green][red][black];
    }
    long res[] = new long[players];
    if(green == 0 && red == 0 && black == 0){
      //player 0 win
      res[0] = 1;
    }else{      
      if(green > 0){
        long next[] = rec(green - 1 , red , black , pnum);
        for(int i = 0 ; i < pnum ; i++){
          res[(i + 1) % pnum] += next[i];
        }
      }
      if(red > 0){
        long next[] = rec(green  , red - 1, black , pnum);
        for(int i = 0 ; i < pnum ; i++){
          res[pnum - 1 - i] += next[i];
        }
      }
      if(black > 0){
        long next[] = rec(green  , red , black - 1, pnum - 1);
        //remove player 0
        for(int i = 1 ; i < pnum ; i++){
          res[i] += next[i - 1];
        }
      }
    }
    return memo[green][red][black] = res;
  }
  public int bestPosition(int players, int green, int red, int black) {
    this.players = players;
    memo = new long[green + 1][red + 1][black + 1][];    
    long winnum[] = rec(green, red, black , players);
    int res = 0;
    for(int i = 1 ; i < winnum.length ; i++)
      if(winnum[res] < winnum[i])
        res = i;
    return res;
  }
}

2009-01-14

SRM 173 Div1 Hard

| 19:25

与えられた点からn個選んだ時に選んだ点の凸包の面積を最大にせよという問題.

  • 候補点は凸包の中から選べばよい
  • 始点を固定した後に、一個前の点と残りの選べる点の個数を状態としてメモ付き探索を行う
  • 再帰式はf(start , p , n) = max_q ( f(start , q , n - 1) + |start-p-q|)と書ける
import java.util.*;

public class ElectronicScarecrows {
  class Point {
    double x, y;

    Point(double a, double b) {
      this.x = a;
      this.y = b;
    }

    @Override
    public String toString() {
      return x + " : " + y;
    }

    double norm() {
      return x * x + y * y;
    }
  }
  double cross(Point a, Point b, Point c) {
    double res = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    return res;
  }
  double cmp(Point a , Point b){
    if(a.x != b.x)return a.x - b.x;
    return a.y - b.y;
  }
  double dist(Point a , Point b){
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return dx * dx + dy * dy;
  }
  List<Point> convexHull(List<Point> ps) {
    List<Point> res = new ArrayList<Point>();
    if(ps.size() < 3)return res;
    int N = ps.size();
    int p = 0;
    for(int i = 1 ; i < N ; i++)
      if(cmp(ps.get(i) , ps.get(p)) < 0)
        p = i;
    boolean used[] = new boolean[N];
    int st = p;
    do{
      int n = -1;
      double dist = 0.0;
      for(int i = 0 ; i < N ; i++){
        if(i == p)continue;
        if(used[i])continue;
        if(n == -1)n = i;
        double cross = cross(ps.get(p) , ps.get(i) , ps.get(n));
        double d  = dist(ps.get(i) , ps.get(p));
        if(cross < 0){
          n = i;
          dist = d;
        }else if(Math.abs(cross) < 1.0E-11){
          if(d > dist){
            dist = d;
            n = i;
          }
        }
      }
      res.add(ps.get(p));
      p = n;
      used[p] = true;
    }while(st != p);
    return res;
  }
  double triarea(Point p0 , Point p1 , Point p2){
    return Math.abs(cross(p0 , p1 , p2)) * 0.5;
  }
  double memo[][];
  Point ps[];
  double rec(int pstart , int prev , int n){
    if(n == 0)return 0.0;
    if(memo[prev][n] >= 0.0)
      return memo[prev][n];
    double res = 0.0;
    int p = (prev + 1) % ps.length;
    while(p != pstart){
      double t = triarea(ps[pstart] , ps[prev] , ps[p]);
      double r = rec(pstart , p , n - 1);
      res = Math.max(res, t + r);
      p = (p + 1) % ps.length;      
    }   
    return memo[prev][n] = res;
  }
  public double largestArea(int[] x, int[] y, int n) {
    List<Point> plist = new ArrayList<Point>();
    for(int i = 0 ; i < x.length ; i++){
      plist.add(new Point(x[i] , y[i]));
    }
    List<Point> hull = convexHull(plist);
    this.ps = hull.toArray(new Point[0]);
    int hs = hull.size();
    double res = 0.0;
    for(int pstart = 0 ; pstart < hull.size() ; pstart++){
      memo = new double[hs][n];
      for(int i = 0 ; i < hs ; i++)
          Arrays.fill(memo[i] , -1);
      for(int p0 = pstart + 1 ; p0 < hs ; p0++){
        double r = rec(pstart , p0  , n - 2);
        res = Math.max(res, r);
      }
    }
    return res;
  }
}

RoberGrotlyRoberGrotly2017/05/08 23:31Amoxicilina Internet Where To Buy Levitra Deezer <a href=http://byuvaigranonile.com>viagra</a> Malegra Amoxicillin Trihydrate 250 Dosage Propecia Zwanger Worden

KennnataKennnata2017/06/19 09:38Order Acticin With Overnight Delivery <a href=http://via100mg.com>Buy Viagra</a> Levitra In Hamburg Letrozole <a href=http://cial40mg.com/buy-cheap-cialis.php>Buy Cheap Cialis</a> Brand Name Propecia Generic Onlineerertiledysfunctionpillss <a href=http://buy-priligy-30mg.priliorder.com>Buy Priligy 30mg</a> Unisom In Singapore

buy kamagra 100mgbuy kamagra 100mg2018/04/05 19:11kamagra shop erfahrungen 2015
<a href="http://kamagrabst.com/">buy kamagra online</a>
kamagra 100mg reviews
<a href="http://kamagrabst.com/">kamagra 100 mg</a>
kamagra kopen
http://kamagrabst.com/
kamagra shop erfahrungen 2017

kamagra 100mgkamagra 100mg2018/04/08 00:23kamagra jelly 100mg
<a href="http://kamagrabst.com/">http://kamagrabst.com/</a>
kamagra usa website
<a href="http://kamagrabst.com/">kamagra soft chewable tablets 100 mg</a>
kamagra oral jelly usage
http://kamagrabst.com/
kamagra cost

DustintofDustintof2018/04/08 19:26cialis 20mg price at walmart
<a href="http://justinpro.com/#">buy cialis</a>
compare cialis prices uk
<a href="http://justinpro.com/#">generic cialis online</a>
cialis generico precio argentina
<a href="http://airvietnamairline.com/#">cialis</a>
cialis prices at walmart
<a href="http://airvietnamairline.com/#">buy cialis</a>
coupons for cialis generic

WilliamFexWilliamFex2018/04/09 12:25buy cialis canada canadian drugstore
<a href="http://justinpro.com/#">buy cialis online</a>
brand cialis meaning in hindi
<a href="http://justinpro.com/#">cialis generic</a>
cialis vs viagra reviews
<a href="http://airvietnamairline.com/#">buy generic cialis online</a>
cialis dosage 40 mg
<a href="http://airvietnamairline.com/#">buy generic cialis online</a>
buy cialis canada canadian drugstore

WilliamFexWilliamFex2018/04/09 19:06generic cialis shipped fedex
<a href="http://coastalseaplanes.com/#">generic cialis online</a>
low cost viagra cialis 5mg
<a href="http://coastalseaplanes.com/#">generic cialis online</a>
maximum daily dose of cialis
<a href="http://northcoastgetaway.com/#">buy generic cialis online</a>
low cost viagra cialis
<a href="http://northcoastgetaway.com/#">buy cialis</a>
5 mg or 20 mg cialis after prostate surgery

WilliamFexWilliamFex2018/04/10 09:45viagra generico in farmacia italiana
<a href="http://amsboatyard.com/#">buy viagra</a>
max viagra dosage recommendations
<a href="http://amsboatyard.com/#">buy viagra</a>
best time to take viagra and cialis
<a href="http://viagrapillq.com/#">viagra</a>
viagra side effects skin rash
<a href="http://viagrapillq.com/#">buy generic viagra</a>
viagra vs cialis vs levitra 2013

WilliamFexWilliamFex2018/04/10 15:55viagra professional 100 mg pills kiwi
<a href="http://amsboatyard.com/#">generic viagra online</a>
viagra dosage
<a href="http://amsboatyard.com/#">buy generic viagra online</a>
generic name for viagra
<a href="http://viagrapillq.com/#">viagra generic</a>
effects of black viagra on blood pressure
<a href="http://viagrapillq.com/#">buy generic viagra</a>
viagra coupons printable cvs

WilliamFexWilliamFex2018/04/11 08:15viagra dosage for best results
<a href="http://amsboatyard.com/#">buy viagra online</a>
viagra cialis cost comparison
<a href="http://amsboatyard.com/#">viagra generic</a>
viagra coupons 2018
<a href="http://viagrapillq.com/#">viagra generic</a>
effects of viagra on blood pressure
<a href="http://viagrapillq.com/#">viagra generic</a>
viagra dosage for dogs

WilliamFexWilliamFex2018/04/11 14:12viagra over counter us
<a href="http://blessingsofbirth.com/#">generic viagra online</a>
viagra side effects low blood pressure
<a href="http://blessingsofbirth.com/#">viagra generic</a>
viagra time take effect
<a href="http://timmonssoftware.com/#">viagra generic</a>
generic viagra soft tabs 50mg
<a href="http://timmonssoftware.com/#">viagra generic</a>
viagra generic brands australia

WilliamFexWilliamFex2018/04/12 02:29taking viagra after prostatectomy
<a href="http://amsboatyard.com/#">generic viagra</a>
female viagra reviews
<a href="http://amsboatyard.com/#">buy generic viagra</a>
viagra dosage reddit
<a href="http://viagrapillq.com/#">buy generic viagra</a>
compare viagra cialis levitra side effects
<a href="http://viagrapillq.com/#">generic viagra online</a>
youtube viagra commercial 2015 actresses

WilliamFexWilliamFex2018/04/12 07:58cialis dosage 20mg or 10mg
<a href="http://coastalseaplanes.com/#">cialis generic</a>
cialis and viagra dosage
<a href="http://coastalseaplanes.com/#">cialis generic</a>
prices for cialis at walmart
<a href="http://northcoastgetaway.com/#">buy generic cialis online</a>
vidalista professional generic cialis 20mg
<a href="http://northcoastgetaway.com/#">generic cialis online</a>
cialis commercial female actors 2016

WilliamFexWilliamFex2018/04/12 17:18buy viagra online in usa
<a href="http://amsboatyard.com/#">viagra</a>
viagra generic walmart cost
<a href="http://amsboatyard.com/#">viagra</a>
como fazer viagra caseiro masculino
<a href="http://viagrapillq.com/#">generic viagra</a>
maximum daily dose of viagra
<a href="http://viagrapillq.com/#">viagra generic</a>
brand viagra without a doctor prescription uk

WilliamFexWilliamFex2018/04/12 22:20female viagra pills 100 mg each month
<a href="http://blessingsofbirth.com/#">buy generic viagra online</a>
youtube viagra commercial 2015 football
<a href="http://blessingsofbirth.com/#">buy viagra</a>
generic viagra professional (sildenafil) 100mg
<a href="http://timmonssoftware.com/#">buy viagra online</a>
viagra soft tab
<a href="http://timmonssoftware.com/#">generic viagra online</a>
woman in viagra commercial wearing jersey

WilliamFexWilliamFex2018/04/13 08:10viagra commercial black actress 2015
<a href="http://blessingsofbirth.com/#">buy generic viagra online</a>
viagra feminino onde comprar
<a href="http://blessingsofbirth.com/#">buy generic viagra online</a>
viagra for women commercial
<a href="http://timmonssoftware.com/#">generic viagra online</a>
natural viagra food list in tamil
<a href="http://timmonssoftware.com/#">buy generic viagra</a>
levitra or viagra forum

WilliamFexWilliamFex2018/04/13 12:43price of cialis 20 mg at cvs
<a href="http://justinpro.com/#">buy cialis online</a>
compare cialis and viagra side effects
<a href="http://justinpro.com/#">cialis</a>
generico do cialis no brasil
<a href="http://airvietnamairline.com/#">buy cialis online</a>
cialis 20 mg tablet price
<a href="http://airvietnamairline.com/#">cialis</a>
cialis levitra staxyn and viagra cost comparison

WilliamFexWilliamFex2018/04/13 22:20natural viagra alternatives foods
<a href="http://amsboatyard.com/#">viagra generic</a>
dosage for generic viagra
<a href="http://amsboatyard.com/#">buy generic viagra</a>
viagra professional chewable
<a href="http://viagrapillq.com/#">buy viagra</a>
generic viagra best
<a href="http://viagrapillq.com/#">buy generic viagra online</a>
generic viagra available walgreens

WilliamFexWilliamFex2018/04/14 03:29cialis coupon for costco
<a href="http://coastalseaplanes.com/#">generic cialis</a>
cialis coupon 2016
<a href="http://coastalseaplanes.com/#">buy generic cialis online</a>
cialis doses 10 mg
<a href="http://northcoastgetaway.com/#">buy generic cialis</a>
super active cialis reviews
<a href="http://northcoastgetaway.com/#">cialis</a>
cialis commercial bathtub

WilliamFexWilliamFex2018/04/14 12:51cialis vs viagra 100mg
<a href="http://coastalseaplanes.com/#">buy generic cialis online</a>
cialis generico precio espaГ±a
<a href="http://coastalseaplanes.com/#">buy cialis online</a>
cialis 20 mg dosage
<a href="http://northcoastgetaway.com/#">buy generic cialis</a>
cialis super active tadalafil
<a href="http://northcoastgetaway.com/#">buy cialis online</a>
side effects of generic cialis

WilliamFexWilliamFex2018/04/14 17:28cialis 5mg daily price in the united states
<a href="http://justinpro.com/#">cialis generic</a>
best price viagra and cialis
<a href="http://justinpro.com/#">buy cialis</a>
when is cialis going generic 2017
<a href="http://airvietnamairline.com/#">cialis</a>
cialis extra dosage 100mg capsules
<a href="http://airvietnamairline.com/#">generic cialis online</a>
generic cialis professional 20 mg

WilliamFexWilliamFex2018/04/15 02:41buy viagra cialis online canada
<a href="http://amsboatyard.com/#">buy viagra</a>
viagra coupons free samples
<a href="http://amsboatyard.com/#">buy viagra online</a>
generic viagra best
<a href="http://viagrapillq.com/#">buy generic viagra</a>
cost per pill for generic viagra in mexico
<a href="http://viagrapillq.com/#">buy viagra</a>
desi viagra price in india

WilliamFexWilliamFex2018/04/15 07:34side effects viagra cialis levitra
<a href="http://amsboatyard.com/#">generic viagra</a>
viagra prices us pharmacy
<a href="http://amsboatyard.com/#">generic viagra</a>
best price generic viagra
<a href="http://viagrapillq.com/#">viagra</a>
generic viagra super active (sildenafil citrate)
<a href="http://viagrapillq.com/#">buy generic viagra online</a>
reviews on female viagra

WilliamFexWilliamFex2018/04/15 16:24viagra generico brasil
<a href="http://blessingsofbirth.com/#">viagra generic</a>
viagra like natural foods
<a href="http://blessingsofbirth.com/#">generic viagra online</a>
female viagra pills walmart
<a href="http://timmonssoftware.com/#">generic viagra online</a>
cialis and viagra dosage
<a href="http://timmonssoftware.com/#">generic viagra online</a>
viagra generico in italia

WilliamFexWilliamFex2018/04/15 21:25viagra feminino onde comprar em bh
<a href="http://amsboatyard.com/#">viagra</a>
female viagra pill online
<a href="http://amsboatyard.com/#">generic viagra online</a>
viagra and cialis best price
<a href="http://viagrapillq.com/#">generic viagra</a>
viagra feminina no brasil
<a href="http://viagrapillq.com/#">viagra</a>
natural viagra foods in urdu

KatDyeluPKatDyeluP2018/04/15 22:43Oral Jelly Kamagra Congestion Nasale Levothyrox No Prescription Viagra Y Antibioticos <a href=http://cheapciali.com>cialis prices</a> Buy Flagyl Over The Counter Amoxicilline Teva 250mg 5ml My Alli Canada

WilliamFexWilliamFex2018/04/16 21:57best time to take viagra for best results
<a href="http://blessingsofbirth.com/#">buy viagra</a>
viagra and cialis dosage and cost comparison between
<a href="http://blessingsofbirth.com/#">generic viagra online</a>
viagra generico preço bh
<a href="http://timmonssoftware.com/#">viagra generic</a>
new viagra commercial asian actress name
<a href="http://timmonssoftware.com/#">buy generic viagra</a>
what is generic viagra professional

WilliamFexWilliamFex2018/04/17 03:07viagra levitra cialis cost comparison
<a href="http://justinpro.com/#">buy cialis</a>
cialis generic in us
<a href="http://justinpro.com/#">buy generic cialis</a>
purchase generic cialis online
<a href="http://airvietnamairline.com/#">buy generic cialis online</a>
buy generic cialis viagra online
<a href="http://airvietnamairline.com/#">cialis</a>
cialis vs viagra vs levitra

WilliamFexWilliamFex2018/04/17 12:15prices of cialis and viagra
<a href="http://amsboatyard.com/#">buy generic viagra online</a>
viagra cialis pharmacy
<a href="http://amsboatyard.com/#">generic viagra</a>
medicamento generico viagra mexico
<a href="http://viagrapillq.com/#">buy viagra</a>
cialis price vs viagra cost
<a href="http://viagrapillq.com/#">viagra</a>
other names for generic viagra

WilliamFexWilliamFex2018/04/17 16:35pfizer brand viagra online
<a href="http://amsboatyard.com/#">buy generic viagra online</a>
viagra medical use
<a href="http://amsboatyard.com/#">buy generic viagra</a>
viagra vs cialis generic
<a href="http://viagrapillq.com/#">buy generic viagra online</a>
what s the maximum dosage for viagra
<a href="http://viagrapillq.com/#">buy generic viagra</a>
viagra prices in us

WilliamFexWilliamFex2018/04/18 02:10comprar viagra generico en espaГ±a contrareembolso
<a href="http://blessingsofbirth.com/#">buy viagra</a>
viagra for women 2017
<a href="http://blessingsofbirth.com/#">buy generic viagra</a>
viagra car commercial youtube
<a href="http://timmonssoftware.com/#">buy generic viagra</a>
viagra coupons rite aid
<a href="http://timmonssoftware.com/#">viagra generic</a>
viagra side effects on women