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

TCO 09 Round 1 Medium

| 04:05

ネットで順序統計量とか調べると公式が載っているのでそれを実装しただけです。

public class KthProbableElement {
  double fact(int n){
    double res = 1.0;
    for(int i = 1 ; i <= n ; i++)
      res *= i;
    return res;
  }
  public double probability(int M, int lowerBound, int upperBound, int N, int K) {
    double res = 0.0;
    double pi = 1.0 * (N - lowerBound + 1) / (upperBound - lowerBound + 1);
    double pii = 1.0 * (N - lowerBound ) / (upperBound - lowerBound + 1);
    for(int k = K ; k <= M ; k++){
      double cmb = fact(M) / (fact(k) * fact(M - k)); 
      double r = Math.pow(pi , k) * Math.pow(1.0 - pi ,M - k);
      r -= Math.pow(pii , k) * Math.pow(1.0 - pii ,M - k);
      res += r * cmb;
    }
    return res;
  }
}

TCO 09 Round 1 Easy

| 04:01

数列の長さlを固定すると、数列の和は初項をaとしたときに(l * a + (l-1) * l / 2)となる.この値を=Nとおいたときにaが正の整数解となればよい。後はlをLから100まで動かしていけばよい。

  public int[] sequence(int N, int L) {
    for(int len = L ; len <= 100 ; len++){
      int s = (len - 1) * len / 2;
      int d = N - s;
      if(d >= 0){
        if(d % len == 0){
          int a = d / len;
          int res[] = new int[len];
          res[0] = a;
          for(int i = 1 ; i < res.length ; i++)
            res[i] = res[i - 1] + 1;
          return res;
        }        
      }
    }
    return new int[0];
  }