Hatena::Grouptopcoder

tsubosakaの日記

2009-03-08

TCO 09 Round 1 Hard

| 04:12

方針としてはあるマス目でのi文字目においての場合の数はそのマスに来れるマスの1個前の場合の数の合計に等しい。また、条件からあるマスに来れないマスというのはそのマスから5*5の部分+中心から幅3の列および行の部分で、この値は列和と行和を前計算すればO(1)で求められるので、すべての場合の数の合計から来れないマスの場合の数を引けばよい。全体の計算量は文字列の長さ*R*C=50 * 300^2 = 4.5 * 10^6で十分に間に合う

public class Unicorn {
  final static int MOD = 1000000007;
  public int countWays(int R, int C, int L, int seed, String word) {
    char[][] chessborad = generate(R, C, L, seed);
    int memo[][] = new int[R][C];
    for(int r = 0 ; r < R ; r++){
      for(int c = 0 ; c < C ; c++){
        memo[r][c] = word.charAt(0) == chessborad[r][c] ? 1 : 0;
      }
    }
    for(int i = 1 ; i < word.length() ; i++){
      int sum = 0;
      for(int r = 0 ; r < R ; r++)
        for(int c = 0 ; c < C ; c++)
          sum = (sum + memo[r][c]) % MOD;
      int rowSum[] = new int[R];
      int colSum[] = new int[C];
      for(int r = 0 ; r < R ; r++)
        for(int c = 0 ; c < C ; c++){
          rowSum[r] = (rowSum[r] + memo[r][c]) % MOD;
          colSum[c] = (colSum[c] + memo[r][c]) % MOD;
        }
      int next[][] = new int[R][C];
      for(int r = 0 ; r < R ; r++){
        for(int c = 0 ; c < C ; c++){
          if(word.charAt(i) != chessborad[r][c])continue;
          int val = sum;
          for(int a = -1 ; a <= 1 ; a++){
            int nr = r + a;
            if(nr < 0 || nr >= R)continue;
            val = (val + MOD - rowSum[nr]) % MOD;
          }
          for(int b = -1 ; b <= 1 ; b++){
            int nc = c + b;
            if(nc < 0 || nc >= C)continue;            
            val = (val + MOD - colSum[nc]) % MOD;
          }
          for(int a = -2 ; a <= 2 ; a += 4){
            for(int b = -2 ; b <= 2 ; b += 4){
              int nr = r + a;
              int nc = c + b;
              if(nr < 0 || nr >= R)continue;
              if(nc < 0 || nc >= C)continue;
              val = (val + MOD - memo[nr][nc]) % MOD;
            }
          }
          for(int a = -1 ; a <= 1 ; a++){
            for(int b = -1 ; b <= 1 ; b++){
              int nr = r + a;
              int nc = c + b;
              if(nr < 0 || nr >= R)continue;
              if(nc < 0 || nc >= C)continue;
              val = (val +  memo[nr][nc]) % MOD;
            }
          }
          next[r][c] = val;
        }
      }
      memo = next;      
    }
    int sum = 0;
    for(int r = 0 ; r < R ; r++)
      for(int c = 0 ; c < C ; c++)
        sum = (sum + memo[r][c]) % MOD;
    return sum;
  }

  private char[][] generate(int R, int C, int L, int seed) {
    char chessborad[][] = new char[R][C];
    int x = seed;
    int d = (65535 / L) + 1;
    for(int r = 0 ; r < R ; r++){
      for(int c = 0 ; c < C ; c++){
        x = (x * 25173 + 13849) % 65536;
        int i = (65 + (x / d));
        chessborad[r][c] = (char)i;
      }
    }
    return chessborad;
  }
}

2009-02-25

*[TCO]TCO 09 Qualification Round 1 Hard

| 00:21

与えられる数がすべて異なるために作れる素数は最小でも3ですべて奇数である。このため和が素数となりえるペアは奇数+偶数の形に限られて、それぞれの数をノードとしてみると二部グラフの最大マッチングをとけばよいことがわかる。


import java.util.*;

public class PrimePairs {
  public int[] matches(int[] numbers) {
    boolean ps[] = new boolean[2001];
    Arrays.fill(ps, true);
    ps[0] = ps[1] = false;
    for(int i = 2 ; i < ps.length ; i++){
      if(!ps[i])continue;
      for(int j = i + i ; j < ps.length ; j += i)
        ps[j] = false;
    }
    int n0 = numbers[0];
    int N = numbers.length;
    List<Integer> left = new ArrayList<Integer>();
    List<Integer> right = new ArrayList<Integer>();
    for(int i = 0 ; i < N ; i++){
      if((n0 % 2) == (numbers[i] % 2))left.add(numbers[i]);
      else right.add(numbers[i]);      
    }
    if(left.size() != right.size()){
      return new int[0];
    }
    boolean adj[][] = new boolean[N][N];
    int ls = left.size();
    for(int i = 0 ; i < left.size() ; i++){
      for(int j = 0 ; j < right.size() ; j++){
        int l = left.get(i);
        int r = right.get(j);
        if(ps[l + r])adj[i][j + ls] = true;        
      }
    }
    List<Integer> lst = new ArrayList<Integer>();
    for(int i = 0 ; i < right.size() ; i++){      
      if(adj[0][i + ls]){
        boolean tmp[][] = new boolean[N][N];
        for(int j = 0 ; j < N ; j++)
          tmp[j] = adj[j].clone();
        for(int j = 0 ; j < N ; j++){
          tmp[0][j] = false;
          tmp[j][i + ls] = false;
        }
        if(bipartite_matching(tmp, ls) + 1 == ls)
          lst.add(right.get(i));        
      }
    }
    Collections.sort(lst);
    int[] res = new int[lst.size()];
    for(int i = 0 ; i < res.length ; i++)
      res[i] = lst.get(i);    
    return res;
  }

  int bipartite_matching(boolean adj[][], int leftSize) {
    int match = 0;
    int matchTo[] = new int[adj.length];
    Arrays.fill(matchTo, -1);
    boolean visited[] = new boolean[adj.length];
    for (int u = 0; u < leftSize; u++) {
      Arrays.fill(visited, false);
      if (augment(adj, u, matchTo, visited))
        match++;
    }
    return match;
  }

  boolean augment(boolean adj[][], int u, int matchTo[], boolean visited[]) {
    if (u < 0)
      return true;
    for(int i = 0 ; i < adj[u].length ; i++){
      if(adj[u][i] && !visited[i]){
        visited[i] = true;
        if (augment(adj, matchTo[i], matchTo, visited)) {
          matchTo[u] = i;
          matchTo[i] = u;
          return true;
        }        
      }
    }
    return false;
  }
}

2009-01-19

SRM 320 Div1 Hard

| 19:08

n*m <= 80なのでmin(n,m) <= 8で一般性を失うことなく短い方を列としてよい.あとは現在の列の状態と配置したcheaterの数を状態としてDP.

すべての場合の数は\binom{n * m}{k}で求まる.なお\binom{80}[20} < 2^63より計算結果はlongに収まる.

import java.math.BigInteger;
import java.util.*;

public class SeatingPlan {
  List<Integer> accept(int m){
    List<Integer> res = new ArrayList<Integer>();
    l: for(int i = 0 ; i < (1 << m) ; i++){
      for(int j = 0 ; j + 1 < m ; j++)
        if((i & (1 <<j)) != 0 && (i & (1 <<(j+1))) != 0)
          continue l;      
      res.add(i);
    }    
    return res;
  }
  public String expectedTrial(int m, int n, int k) {
    if(m > n)return expectedTrial(n, m, k);
    List<Integer> alist = accept(m);
    int accept[] = new int[alist.size()];
    for(int i = 0 ; i < accept.length ; i++)
      accept[i] = alist.get(i);
    long memo[][] = new long[1 << m][k + 1];
    memo[0][0] = 1;   
    for(int col = 0 ; col < n ; col++){
      long next[][] = new long[1 << m][k + 1];
      for(int S : accept){
        for(int T : accept){
          if((S & T) != 0)continue;
          int i = Integer.bitCount(S);
          for(int a = 0 ; a <= k ; a++){
            if(a + i > k)break;
            next[S][a + i] += memo[T][a];
          }
        }
      }
      memo = next;
    }
    long sum = 0;
    for(int i = 0 ; i < memo.length ; i++)
      sum += memo[i][k];
    if(sum == 0)return "Impossible!";
    long tot = comb(m * n , k);
    return toStr(tot , sum);
  }
  long comb(int n , int k){
    long c[][] = new long[n + 1][n + 1];
    c[0][0] = 1;
    for(int i = 1 ; i <= n ; i++){
      c[i][0] = 1;
      for(int j = 1 ; j <= n ; j++){
        c[i][j] = c[i-1][j-1] + c[i-1][j];
      }
    }
    return c[n][k];
  }
  String toStr(long t , long s){
    BigInteger a = BigInteger.valueOf(t);
    BigInteger b = BigInteger.valueOf(s);
    BigInteger g = a.gcd(b);
    a = a.divide(g);
    b = b.divide(g);
    return a.toString() +"/" + b.toString();
  }
}

2009-01-17

SRM 310 Div1 Hard

| 18:20

すでに使った箱の集合といちばん上の箱の状態をキーとしてDPする.箱の状態はどこをz軸にするかの3通り考えれば十分なのでキーの数は2^n * 3n でn <= 15より実行時間内に解ける.

public class BoxTower {
  public int tallestTower(int[] x, int[] y, int[] z) {
    int n = x.length;
    int dp[][] = new int[1 << n][3 * n];
    int ws[][] = new int[3 * n][2];
    int hs[] = new int[3 * n];
    for(int i = 0 ; i < n ; i++){
      dp[1 << i][i] = hs[i] = z[i];
      ws[i][0] = Math.min(x[i], y[i]);
      ws[i][1] = Math.max(x[i], y[i]);
      dp[1 << i][i + n] = hs[i + n] = y[i];
      ws[i + n][0] = Math.min(x[i], z[i]);
      ws[i + n][1] = Math.max(x[i], z[i]);
      dp[1 << i][i + 2 * n] = hs[i + 2 * n] = x[i];
      ws[i + 2 * n][0] = Math.min(y[i], z[i]);
      ws[i + 2 * n][1] = Math.max(y[i], z[i]);
    }
    for(int S = 0 ; S < dp.length ; S++){
      for(int j = 0 ; j < 3 * n; j++){
        int tj = j % n;
        if((S & (1 << tj)) == 0)continue;
        for(int k = 0 ; k < 3 * n ; k++){
          int tk = k % n;
          if(((S & (1 << tk))) != 0)continue;
          int next = (S | (1 << tk));
          if(ws[k][0] <= ws[j][0] && ws[k][1] <= ws[j][1])
            dp[next][k] = Math.max(dp[next][k], dp[S][j] + hs[k]);          
        }
      }
    }
    int res = 0;
    for(int d[] : dp){
      for(int i : d)res = Math.max(i, res);
    }
    return res;
  }
}

2009-01-15

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