2009-02-08
SRM 434 Div1 Medium
変換する文字の種類は総和が最も大きくなるように上から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(); } }
コメントを書く