Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-25SRM362, SRM363 (Practice)

SRM 363 MirrorNumber

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

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

  • 方針を検討
    • DPする?
      • 先頭に2をつけたら後ろに5をつけなきゃいけない。
      • 「オーバーしたかどうか」フラグを管理するのが難しそう
    • 求めるべき数はそんなに大きくないはず。全探索でよさそう
      • 5^9 * 2 = 4Mぐらいだろ、だいじょぶだいじょぶ!
  • 実装
    • 10^18を突っ込むとTLEする
      • あれ!?
      • 文字列操作コストがそれなりに重いのかなぁ
    • やっぱりDPしなきゃダメか?
  • Editorial読むと全探索って書いてある
    • 選んだ数字を配列に入れてけばいいらしい。数字のまま処理するべし
    • 長さを決め打ちするって発想も出てこなかったなぁ
public class MirrorNumber {
	long A, B;
	int cnt;
	int[] pre = {0, 1, 8, 2, 5};
	int[] suf = {0, 1, 8, 5, 2};
	int[] digits = new int[50];
	
	public void dfs(int l, int f, int t) {
		if (f < t) {
			for (int i = (f == 0) ? 1 : 0 ; i < 5 ; i++) {
				digits[f] = pre[i];
				digits[t] = suf[i];
				dfs(l, f+1, t-1);
			}
		} else if (f == t) {
			for (int i = 0 ; i < 3 ; i++) {
				digits[f] = pre[i];
				dfs(l, f+1, t-1);
			}
		} else {
			long val = 0;
			for (int i = l ; i >= 0 ; i--) {
				val *= 10;
				val += digits[i];
			}
			if (A <= val && val <= B) {
				cnt++;
			}
		}
	}
	
	public int count(String a, String b) {
		A = Long.valueOf(a);
		B = Long.valueOf(b);
		for (int i = 0 ; i < 18 ; i++) {
			dfs(i, 0, i);
		}
		return cnt;
	}
}