TCO07 Round 2

1問も解けませんでした．

• 250: 問題の意味が分かってない
• 500: Greedyでいけると思いこんで，そのまま終了．
• 1000: 近似の長さLを1からnumber.lengthまで増やしていって，長さがLのときのnumberの最も近い近似が許容誤差をみたすかどうかを調べるという方針でいこうと思ったのだけど間に合わず．

一応，後付けで補足すると色々コードを見たところ1000ptの最も楽な実装方法としてはnumberをBigDecimalに変換して，そいつにたいしてnumber.setScale(scale,RoundingMode.DOWN)，number.setScale(scale,RoundingMode.UP)(scaleは[0-number.scale]を動く)を考えて，その中で許容誤差を満たす一番長さが小さいものを選ぶ．(ただし, (k = 2,number="10000")のようなケースでは解は"9999".length() = 4となるのでその部分だけ別に計算する)

コードは次のようになる

import java.math.*;
public class Neaten {
	public static int shortest(int k, String number){
		BigDecimal num = new BigDecimal(number);
		BigDecimal absErr = new BigDecimal(BigInteger.ONE,k); 
		BigDecimal relErr = absErr.multiply(num);
		BigDecimal err = absErr.max(relErr);
		int min = len(num);
		int index = number.indexOf('.') - 1;
		if(index<0)index = number.length() - 1;
		BigDecimal nearInt = new BigDecimal(BigInteger.ONE, - index);
		nearInt = nearInt.subtract(BigDecimal.ONE);
		if(inErr(err,num,nearInt))min = Math.min(len(nearInt), min);
		for(int i=0;i<=num.scale();i++){
			BigDecimal down = num.setScale(i,RoundingMode.DOWN);
			BigDecimal up =   num.setScale(i,RoundingMode.UP);
			if(inErr(err,num,down))min = Math.min(len(down), min);
			if(inErr(err,num,up))min = Math.min(len(up), min);
		}
		return min;
	}
	static int len(BigDecimal n){
		String s = n.toString();
		return s.startsWith("0.")?s.length()-1:s.length();
	}
	static boolean inErr(BigDecimal err,BigDecimal n1,BigDecimal n2){
		return (n1.subtract(n2).abs()).compareTo(err)<0;
	}
}