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-08

SRM 434 Div1 Easy

| 04:03

初項の場所と列行の公差を全探索するだけ。ただし、数列は最長のものだけではなくて部分列もチェックする必要がある。そこを忘れていた人がかなりいた。あとSystem Testで落ちていた人で多分sqrtの誤差で落ちているような人がいた。

public class FindingSquareInTable {
  public int findMaximalSquare(String[] table) {
    int H = table.length;
    int W = table[0].length();
    int t[][] = new int[H][W];
    for(int i = 0 ; i < H ; i++)
      for(int j = 0 ; j < W ; j++)
        t[i][j] = table[i].charAt(j) - '0';
    int square[] = new int[32000];
    for(int i = 0 ; i < square.length ; i++){
      square[i] = i * i;
    }
    int max = -1;
    for(int sx = 0 ; sx < W ; sx++){
      for(int sy = 0 ; sy < H ; sy++){
        for(int dx = -9 ; dx <= 9 ; dx++){
          for(int dy = -9 ; dy <= 9 ; dy++){
            if(dx == 0 && dy == 0)continue;
            int x = sx;
            int y = sy;
            int v = t[y][x];
            while(true){
              x = x + dx;
              y = y + dy;
              if(x < 0 || y < 0 || x >= W || y >= H)break;
              v = v * 10 + t[y][x];
              if(max < v && Arrays.binarySearch(square, v) >= 0){
                max = v;
              }
            }
            if(max < v && Arrays.binarySearch(square, v) >= 0){
              max = v;
            }
          }
        }
      }
    }
    return max;
  }
}