Hatena::Grouptopcoder

tsubosakaの日記

2009-03-08

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

2009-02-25

TCO 09 Qualification Round 1 Easy

| 00:10

各数に関して自分より大きいものが何個あるかを数えるだけ。同じ場合は前にあるもののみを数える


public class SortingWithPermutation {
  public int[] getPermutation(int[] a) {
    int N = a.length;
    int[] res = new int[N];
    for(int i = 0 ; i < N ; i++){
      int cnt = 0;
      for(int j = 0 ; j < N ; j++)
        if((a[i] > a[j]) ||
           (a[i] == a[j] && i > j))
          cnt++;      
      res[i] = cnt;
    }
    return res;
  }
}

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

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

SRM 320 Div1 Easy

| 18:59

"12!"とか"3!!"などの形式で数字が二つ与えられるので大小比較しろという問題.

!の数が等しければ係数の比較をすればよく,そうでないときは!の数が大きい方を一段階計算して再帰的に比較する.ただ"10000!"とかを計算すると途中でオーバフローするので他方の係数よりも大きくなったときに打ち切る必要があるのと,"0!!"の扱いに気をつける必要がある.

public class ExtraordinarilyLarge {
  class Fact{
    long val;
    long fnum;
    Fact(String str){
      int i = str.indexOf('!');
      if(i < 0){
        val = Long.parseLong(str);
        fnum = 0;
      }else{
        val = Long.parseLong(str.substring(0, i));
        fnum = str.length() - i;
      }
      if(val == 0 && fnum > 0){
        val = 1;
        fnum = 0;
      }
    }
    Fact(long v  , long n){
      val = v; fnum = n;
    }
    long cmp(Fact f){
      if(fnum == f.fnum)
        return val - f.val;     
      if(fnum < f.fnum)return - f.cmp(this);
      long r = 1;
      for(long v = 1 ; v <= val ; v++){
        r *= v;
        if(r > f.val)return 1;
      }
      Fact a = new Fact(r , fnum - 1);
      return a.cmp(f);
    }
  }
  public String compare(String x, String y) {
    Fact fx = new Fact(x);
    Fact fy = new Fact(y);
    long c = fx.cmp(fy);
    System.err.println(c);
    if(c > 0)return "x>y";
    else if(c < 0)return "x<y";    
    return "x=y";
  }
}