tsubosakaの日記

SRM 434 Div1 Medium

SRM, Medium, Math, Greedy | 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();
  }
}