Hatena::Grouptopcoder

tsubosakaの日記

2009-02-08

SRM 434 Div1 Medium

| 04:07

変換する文字の種類は総和が最も大きくなるように上からk個選べばよい。

javaだとnew BigInteger(String s , int radix)で指定した基数でのString表現をBigIntegerにできて、そのBigIntegerをtoString(int radix)で指定した基数のString表現に変換できるので非常に簡単。

最初、k種類の文字が全部Zに変わるのではなくて、k個の文字をZに変えると勘違いしていてはまった。

public class HexatridecimalSum {
  BigInteger sum(char carr[][]){
    BigInteger sum = BigInteger.ZERO;
    for(char[] a : carr){
      sum = sum.add(new BigInteger(new String(a) , 36));
    }
    return sum;
  }
  void replaceToZ(char carr[][] , char c){
    for(int i = 0 ; i < carr.length ; i++)
      for(int j = 0 ; j < carr[i].length ; j++)
        if(carr[i][j] == c)
          carr[i][j] = 'Z';
  }
  public String maximizeSum(String[] numbers, int k) {
    char carr[][] = new char[numbers.length][];
    for(int i = 0 ; i < numbers.length ; i++){
      carr[i] = numbers[i].toCharArray();
    }
    for(int i = 0 ; i < k ; i++){
      BigInteger max = BigInteger.ZERO;
      char mc = ' ';
      for(int d = 0 ; d < 36 ; d++){
        char c = '0';
        if(d < 10)c = (char)('0' + d);
        else c = (char)('A' + d - 10);
        char tmp[][] = new char[numbers.length][];
        for(int j = 0 ; j < numbers.length ; j++){
          tmp[j] = carr[j].clone();
        }
        replaceToZ(tmp, c);
        BigInteger s = sum(tmp);
        if(s.compareTo(max) > 0){
          max = s;
          mc = c;
        }
      }
      replaceToZ(carr, mc);
    }
    return sum(carr).toString(36).toUpperCase();
  }
}

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

SRM 434 Div1

| 03:55

250は簡単なんだけど、はまるポイントがいくつかあって落とした。

500はJavaのBigIntegerを用いると非常に簡単な問題だった。

250は自分でやった間違いをほかの人で探したらかなりあって、5回中4回challenge成功で成績は結構よかった。

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/tsubosaka/20090208