Hatena::Grouptopcoder

tsubosakaの日記

2009-01-15

SRM 286 Div1 Easy

| 09:36

当たる確率のあるパターンは現在リーチになっているものだけなので期待値の独立性から(リーチになっているものの賞金総額) / (残りのボールの数)を計算すればよい.

import java.util.*;
public class ExtraBall {
  public double expectedPayout(int[] card, int[] balls, String[] patterns,
      int[] prizes) {
    Arrays.sort(balls);
    int cs[] = new int[card.length];
    for(int i = 0 ; i < card.length ; i++)
      if(Arrays.binarySearch(balls, card[i]) >= 0)
        cs[i] = 1;
    double tot = 0.0;
    for(int p = 0 ; p < patterns.length ; p++){
      int diff = 0;
      String pattern = patterns[p];
      for(int j = 0 ; j < cs.length ; j++)
        if(cs[j] == 0 && pattern.charAt(j) == 'X')
          diff++;
      if(diff == 1)
        tot += prizes[p];      
    }
    double res = tot / (75.0 - balls.length);
    return res;
  }
}

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

SRM 286 Div1 Hard

| 09:26

(x,y)を選んで出来る文字列は(x % C , y % R)を選んで出来る文字列と等しいのでC*R個の文字列に関するマッチを調べればよい.

そうすると,長さ1000ぐらいの文字列が1000個程度与えられるのでその中から与えられたパターンにマッチするものはいくつあるかという問題に帰着できる.

パターンは複数あるがAho-Corasick algorithmを用いれば文字列の長さに比例する程度の時間で実行できる.手元の実験ではKMPをもちいるより5倍程度速かった.

import java.util.*;

public class InfiniteSoup {
  static class PMA {
    PMA next[];
    PMA fail;
    List<Integer> accept;
    PMA() {
      next = new PMA[256];
      accept = new ArrayList<Integer>();
    }
  }

  static PMA buildPMA(char p[][], int size) {
    PMA root = new PMA();
    for (int i = 0; i < size; i++) {
      PMA t = root;
      for (int j = 0; j < p[i].length; ++j) {
        char c = p[i][j];
        if (t.next[c] == null)
          t.next[c] = new PMA();
        t = t.next[c];
      }
      t.accept.add(i);
    }
    for(int c = 'a' ; c <= 'z' ; c++)
      if(root.next[c] == null)
        root.next[c] = root;
    Queue<PMA> Q = new LinkedList<PMA>();
    for (int c = 'a'; c <= 'z'; c++) {
      if (root.next[c] != root) {
        root.next[c].fail = root;
        Q.add(root.next[c]);
      }
    }
    while (!Q.isEmpty()) {
      PMA t = Q.poll();
      for (int c = 'a'; c <= 'z'; c++) {
        if (t.next[c] != null) {
          Q.add(t.next[c]);
          PMA r = t.fail;
          while (r.next[c] == null)
            r = r.fail;
          t.next[c].fail = r.next[c];
          t.next[c].accept.addAll(r.next[c].accept);
        }
      }
    }
    return root;
  }

  static void match(char t[], PMA v, int result[]) {
    int n = t.length;
    for (int i = 0; i < n; i++) {
      char c = t[i];
      while (v.next[c] == null)
        v = v.fail;
      v = v.next[c];
      for (int j : v.accept){
        result[j] = 1;
      }
    }
  }

  static int kmp(char t[], char p[], int fail[]) {
    int n = t.length;
    int m = p.length;
    for (int i = 0, k = 0; i < n; i++) {
      while (k >= 0 && p[k] != t[i])
        k = fail[k];
      if (++k >= m) {
        return 1;
      }
    }
    return 0;
  }

  static int[] buildFail(char p[]) {
    int m = p.length;
    int fail[] = new int[m + 1];
    int j = fail[0] = -1;
    for (int i = 1; i <= m; i++) {
      while (j >= 0 && p[j] != p[i - 1])
        j = fail[j];
      fail[i] = ++j;
    }
    return fail;
  }

  void getRay(char grid[][], int x, int y, char ray[]) {
    int cx = 0;
    int cy = 0;
    for (int i = 0; i < ray.length; i++) {
      ray[i] = grid[cy][cx];
      cx += x;
      cy += y;
      if (cy >= grid.length)
        cy -= grid.length;
      if (cx >= grid[0].length)
        cx -= grid[0].length;
    }
  }

  static int gcd(int a, int b) {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }

  public int[] countRays(String[] g, String[] words, int k) {
    int H = g.length;
    int W = g[0].length();
    int wnum = words.length;
    char grid[][] = new char[H][W];
    for (int i = 0; i < grid.length; i++)
      grid[i] = g[i].toCharArray();
    boolean check[][] = new boolean[H][W];
    int memo[][][] = new int[H][W][wnum];
    int res[] = new int[wnum];
    char ray[] = new char[H * W + 50];
    char ws[][] = new char[wnum][];
    for (int i = 0; i < ws.length; i++)
      ws[i] = words[i].toCharArray();    
    PMA pma = buildPMA(ws, wnum);
    for (int x = 0; x <= k; x++) {
      for (int y = 0; y <= k; y++) {
        int gcd = gcd(x, y);
        if (gcd != 1) continue;
        int a = x % W;
        int b = y % H;
        if (!check[b][a]) {
          getRay(grid, a, b, ray);
          match(ray, pma, memo[b][a]);
          check[b][a] = true;
        }
        for (int i = 0; i < wnum; i++)
          res[i] += memo[b][a][i];
      }
    }
    return res;
  }
}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/tsubosaka/20090115