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

JospehmoilaJospehmoila2019/01/30 07:27buy cialis in mexico
cialis without a rx
buy cialis with dapoxetine online
cialis sin receta medica

best cialis online order
cialis original brand name sale
buy cialis online scams
cialis from canada with a prescription
https://stowe365.com/#Buy-Cialis-20-mg

JospehmoilaJospehmoila2019/01/30 16:30cialis thailand buy
typical cialis prescription
order cheap cialis
canadian pharmacy cialis 20mg

cialis super active 20mg pills
swiss medical cialis
cialis for women free sample
z 14 order cialis super active online
https://stowe365.com/#Buy-Cialis

JospehmoilaJospehmoila2019/01/31 01:32canadian brand label cialis
bay cialis fast shipping
cialis 20 mg effects
cialis for sale without prescription

buy cialis in nigeria
cialis purchace on line fast no rx
genuine brand name cialis
buy cialis soft tabs information
https://stowe365.com/#Buy-Cialis

JospehmoilaJospehmoila2019/01/31 11:59what is correct dosage for cialis
do broken cialis work
current price of cialis
cialis discount paris

cialis hearing loss
bootleg cialis
acquisto online cialis originale
rui products cialis review
https://stowe365.com/#Buy-Cialis

JospehmoilaJospehmoila2019/01/31 23:26real cialis canadian pharmacy
cialis tablets for sale
dove posso acquistare cialis online
best buy cialis online

cialis kanada
5mg daliy cialis reviews
high price of cialis
cialis experience
https://stowe365.com/#Buy-Cialis-20-mg

JospehmoilaJospehmoila2019/02/01 13:50cialis online.com
once a day cialis cheap
generic cialis 99cents
best place to buy cialis online reviews

get a prescription to buy brand cialis
cialis drug information
lloyds pharmacy cialis price
usa overnight pharmacy cialis
https://stowe365.com/#Buy-Cialis-20-mg

DavidtogDavidtog2019/02/02 23:43cialis online apotheke
cheap generic female cialis
<a href="http://kaivanrosendaal.com/">cialis vs viagra</a>
cialis 20 mg coupon
buy cialis chennai
<a href=http://kaivanrosendaal.com>cialis purchasing</a>
rite aid pharmacy cialis
online apotheke cialis kaufen
http://kaivanrosendaal.com/#Buy-Cheap-Cialis-Online

DavidtogDavidtog2019/02/03 08:52cialis tienda online
brand name cialis online
<a href="http://kaivanrosendaal.com">cialis from canada</a>
cialis_2.5_mg_online
selling cialis on craigslist
<a href=http://kaivanrosendaal.com/>cialis tadalafil</a>
cheap cialis extra strength
best place to buy cialis online yahoo
http://kaivanrosendaal.com/#cialis-canada

DavidtogDavidtog2019/02/03 23:29purchase cialis in south africa
men's health online cialis
<a href="http://kaivanrosendaal.com">cialis coupons printable</a>
cialis prescription dosage
cialis forums
<a href=http://kaivanrosendaal.com/>cialis generic availability</a>
is generic cialis legal
prescription cost for cialis
http://kaivanrosendaal.com/#Buy-Cheap-Cialis

DavidtogDavidtog2019/02/04 07:44cialis professional vs regular cialis
apotheke_cialis_schweiz
<a href="http://kaivanrosendaal.com/">Buy Cheap Cialis</a>
comprare il cialis online
cialis soft online kaufen
<a href=http://kaivanrosendaal.com/>what is cialis</a>
cialis effectiveness review
rayh health care cialis
http://kaivanrosendaal.com/#cialis-for-daily-use

DavidtogDavidtog2019/02/04 18:06import cialis
cialis no prescription montreal
<a href="http://kaivanrosendaal.com">cialis for daily use</a>
cialis commercial actor
buy cialis forum
<a href=http://kaivanrosendaal.com>cialis reviews</a>
cialis.60mg.sale
purchase cialis for daily use online
http://kaivanrosendaal.com/#200-cialis-coupon

DavidtogDavidtog2019/02/05 18:04costco price for cialis
cialis e-shops europe
<a href="http://kaivanrosendaal.com">Buy Cheap Cialis Online</a>
cialis von lilly
buy cialis with no perscription
<a href=http://kaivanrosendaal.com/>cialis manufacturer coupon</a>
cialis online singapore
canada law on cialis prescription
http://kaivanrosendaal.com/#cialis-prices

DavidtogDavidtog2019/02/06 03:19cialis black no prescription
buy cialis 10mg australia
<a href="http://kaivanrosendaal.com">discount cialis</a>
buy cialis online with discover card
cialis generico farmacia italiana
<a href=http://kaivanrosendaal.com>online cialis</a>
cialis no prescription needed canada
buy cialis in florida
http://kaivanrosendaal.com/#cialis-coupon

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

WilliamTagWilliamTag2019/02/02 11:26cialis over night
medicus group buy cialis
<a href=https://greatwinesgrandhouses.com>Cheap cialis buy online</a>
does cialis get you hard
cheapest cialis 20mg
https://kellyannehulme.com
buy cialis montreal
generic cialis in 2.5mg daily tablets
<a href=https://kellyannehulme.com>20 mg cialis</a>
lilly cialis without prescription
cialis brand name usa price
https://greatwinesgrandhouses.com

WilliamTagWilliamTag2019/02/02 11:26cialis ads
buying cialis in canada online
<a href=https://greatwinesgrandhouses.com>buy Cialis 20 mg</a>
liquid cialis does it work
cialis and avodart
https://kellyannehulme.com
what does cialis cost in mexico
cialis venezuela
<a href=https://greatwinesgrandhouses.com>Cheap cialis</a>
the cheapest cialis online
headache after cialis
https://greatwinesgrandhouses.com

ArnoldNizArnoldNiz2019/02/05 20:50canada drug generic cialis
buy generic cialis from canada
<a href="http://xcialisxx.com">Cheap Cialis</a>
snort cialis
cialis online con ricetta
<a href="http://cialistlm.com">Cheap Cialis buy</a>
brand cialis online mastercard
quick ship cialis
<a href="http://xcialisxx.com">Cheap Cialis</a>

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