Hatena::Grouptopcoder

tsubosakaの日記

2009-01-22

SRM 433 Div1 Easy

| 23:24

すべての順列とすべてのシフトに対して条件をチェックすると8! * (160^2)が約10億で間に合わない.ただ,手元でテストした場合はテストケースだけだと2秒ぎりぎりぐらいで答えがでるので気づかなかったりする.

簡単な解決策としては7! * (160^2)であれば間に合うので先頭の文字を固定して,結果を文字列の数倍してやればよい.

public class MagicWords {
  boolean check(String str , int K){
    int cnt = 0;
    int n = str.length() / 2;
    for(int j = 0 ; j < n ; j++){
      boolean f = true;
      for(int i = 0 ; i < n ; i++){
        if(str.charAt(i) != str.charAt(i + j)){
          f = false;
          break;
        }
      }
      if(f)cnt++;
    }
    return cnt == K;
  }
  public int count(String[] S, int K) {
    int n = S.length;
    int a[] = new int[S.length];
    for(int i = 0 ; i < n ; i++)
      a[i] = i;
    int cnt = 0;
    do{
      if(a[0] != 0)break;
      StringBuilder sb = new StringBuilder();
      for(int j = 0 ; j < S.length ; j++){
        sb.append(S[a[j]]);
      }
      String str = sb.toString();
      if(check(str + str, K))cnt++;
    }while(nextPermutation(a));
    return cnt * a.length;
  }
  public static boolean nextPermutation(int[] a) {
    int n = a.length;
    int i = n - 2;
    for (; i >= 0; i--) {
      if (a[i] < a[i + 1])
        break;
    }
    if (i < 0)
      return false;
    for (int j = n - 1; j >= i; j--) {
      if (a[i] < a[j]) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
        break;
      }
    }
    for (int j = i + 1; j < (n + i + 1) / 2; j++) {
      int temp = a[j];
      a[j] = a[n + i - j];
      a[n + i - j] = temp;
    }
    return true;
  }
}

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

2009-01-14

SRM 250 Div1 Easy

| 20:22

書いてある通りにやるだけ

public class LanguageRecognition {
  int freq(String s , char c){
    int cnt = 0;
    for(char ch : s.toCharArray())
      if(c == ch)
        cnt++;
    return cnt;
  }
  double diff(String a , String b){
    double sum = 0.0;
    for(char c = 'a' ; c <= 'z' ; c++){
      double fa = freq(a , c) * 1.0 / a.length();
      double fb = freq(b , c) * 1.0 / b.length();
      sum += (fa - fb) * (fa - fb);
    }
    return sum;
  }
  String normalize(String str){
    str = str.toLowerCase();
    str = str.replaceAll("[^a-z]", "");
    return str;
  }
  public int whichLanguage(String[] languages, String text) {
    text = normalize(text);
    for(int i = 0 ; i < languages.length ; i++)
      languages[i] = normalize(languages[i]);
    double ds[] = new double[languages.length];
    int res = 0;
    for(int i = 0 ; i < ds.length ; i++){
      ds[i] = diff(languages[i] , text);
      if(ds[i] + 1.0E-11 < ds[res]){
        res = i;
      }
    }
    return res;
  }
}

SRM 173 Div1 Easy

| 19:25

書いてある通りにやるだけ

public class WordForm {
  public String getSequence(String word) {
    int n = word.length();
    char arr[] = new char[n];
    String vs = "aiueo";
    for(int i = 0 ; i < n ; i++){
      char c = word.charAt(i);
      c = Character.toLowerCase(c);
      if(vs.indexOf(c) >= 0){
        arr[i] = 'V';
      }else if(c == 'y' && i > 0 && arr[i-1] != 'V'){
        arr[i] = 'V';
      }else{
        arr[i] = 'C';
      }
    }
    return shrink(arr);
  }
  String shrink(char arr[]){
    char prev = ' ';
    String res = "";
    for(int i = 0 ; i < arr.length ; i++){
      if(arr[i] != prev){
        res += arr[i];
      }
      prev = arr[i];
    }
    return res;
  }
}

RoberGrotlyRoberGrotly2017/05/08 23:31Amoxicilina Internet Where To Buy Levitra Deezer <a href=http://byuvaigranonile.com>viagra</a> Malegra Amoxicillin Trihydrate 250 Dosage Propecia Zwanger Worden