Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-21SRM367 (Practice)

SRM 367 ObtainingDigitK

|  SRM 367 ObtainingDigitK - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 367 ObtainingDigitK - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8181

  • 方針を検討
    • 一番下の桁だけ見ればいいんじゃないの
    • 書いてサンプル合った
  • いや、待てよ
    • 例えば "15", 2 のとき、最適は 5 を足して十の位を 2 にすべき
    • 危ない危ない。繰り上がりを考慮したコードに書き換える。
  • WA
    • "99999", 1 で死んでた
    • そうか、桁がひとつ増える場合を考慮してなかった
    • 先頭に '0' を付加したら通った
  • 他の人のコード見る
    • みんなBigIntegerでやってる・・・
      • そもそも求める数は高々9だよね。
      • 1〜9までの数字を足して k が含まれてるかどうか見ればいい
    • ライブラリゲーかよ、くそっ
public class ObtainingDigitK {
	public int minNumberToAdd(String originalNumber, int k) {
		originalNumber = '0' + originalNumber; 
		int len = originalNumber.length();
		int min = 99;
		for (int i = len-1 ; i >= 1 ; i--) {
			if (originalNumber.charAt(i) - '0' == k) {
				return 0;
			}
		}
		int c = (k - (originalNumber.charAt(len-1) - '0'));
		min = Math.min(min, (c < 0) ? c + 10 : c);
		
		for (int i = 0 ; i < len ; i++) {
			int d = originalNumber.charAt(i) - '0';
			if ((d == 9 && k == 0) || (k - d == 1)) {
				int nadd = 0;
				for (int j = i+1 ; j < len ; j++) {
					int e = originalNumber.charAt(j) - '0';
					if (e == 9) {
						if (len - 1 - j == 0) {
							min = Math.min(min, 1);
						}
						continue;
					} else {
						if (len - 1 - j >= 1) {
							break;
						} else {
							nadd = 10 - e;
							min = Math.min(nadd, min);
						}
					}
				}
			}
		}
		return min;
	}
}