Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-26SRM360, SRM361 (Practice)

SRM 361 ReverseDistance

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

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

  • 方針を検討
    • DP?状態の持ち方がわからない・・・
    • よく考えると求めるべき数の左半分が決まれば右半分も自動的に決まるので全探索でよさそう
      • 証明はできないけど求めるべき数の桁数は最大でもdifferenceの2倍程度な気がする
      • なので計算すべき量は O(10^6+α) ぐらいだろう
  • 実装。
    • 文字列インデックス指定ミスでしばらくハマる・・・
    • サンプル通った。
  • 最大ケース(900000?)を突っ込んでみる
    • 0.5sで終わる。答えも正しそう。
    • これは大丈夫だろ、出しちゃえ!
  • 再度戻ってくる。コード見直し
    • 繰り下がり処理ミスってる!
      • 繰り下がりフラグを立てたまま再帰から戻ってくるときに戻してない
    • 修正して再提出。なんでこれでサンプル通ったの・・・?
public class ReverseDistance {
	long diff;
	String dif;
	int dlen;
	int len;
	int[] arr;
	int[] flg;
	long min;
	
	public void dfs(int i) {
		if (i >= (len)/2) {
			long number = 0;
			for (int j = len-1 ; j >= 0 ; j--) {
				number *= 10;
				number += arr[j];
			}
			String rev = new StringBuffer(String.valueOf(number)).reverse().toString();
			long revnumber = Long.valueOf(rev);
			if (number - revnumber == diff) {
				min = Math.min(min, number);
			}
			return;
		}
		for (int d = (i == 0) ? 1 : 0 ; d <= 9 ; d++) {
			arr[len-i-1] = d;
			arr[i] = d + (dif.charAt(dif.length()-i-1) - '0') + flg[i];
			if (arr[i] >= 10) {
				flg[i+1] = 1;
				arr[i] -= 10;
			} else {
				flg[i+1] = 0;
			}
			dfs(i+1);
		}
	}
	public String find(int difference) {
		diff = difference; 
		dif = String.valueOf(difference);
		dlen = dif.length();
		dif = "000000000000000000000000000000" + dif;
		for (int i = dlen ; i <= Math.min(12, dlen*2) ; i++) {
			arr = new int[i];
			flg = new int[i];
			len = i;
			min = Long.MAX_VALUE;
			dfs(0);
			if (min != Long.MAX_VALUE) {
				return String.valueOf(min);
			}
		}
		return "NONE";
	}
}