Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-28SRM300台を練習していく part5

SRM 300 JumpyNum

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

まずn桁目の数字がdであるとき、d00...00 〜 d99...99 までのJumpyNumを数える変数dp[n][d]を用意しておく。この数はDPにより求められる。更新式は以下の通り。

for (int j = 0 ; j <= 9 ; j++) {
  if (Math.abs(j - d) >= 2) {
    dp[n][d] += dp[n-1][j]
  }
}

そして、num以下のJumpyNumの数を求める関数をcount(int num)とおくと、

求める答えは count(high) - count(low-1) となる。←ここまでは自力でやった

countを求めるアプローチは以下の通り。


まず、1〜9, 10〜99, 100〜999 , ... , 10...00〜99...99 のJumpyNumの数を、10^(numの桁数 - 1) - 1 まで求める。

次に、10^(numの桁数 - 1) から (numの先頭の桁の数) * 10^(numの桁数 - 1) - 1 までのJumpyNumの数を求める。

そして最後に、numの桁を最初から固定しながら、(numの先頭の桁の数) * 10^(numの桁数 - 1) から num までのJumpyNumの数を求める。

このとき、固定された桁同士がJumpyNumの条件を満たさなくなったら、その場でループを抜ける。

これら全ての和が求める数になる。

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


public class JumpyNum {
	long[][] dp = new long[15][10];

	public long count(int num) {
		if (num == 0) {
			return 0;
		}
		long count = 0;
		String snum = String.valueOf(num);
		int keta = snum.length();
		for (int i = 1 ; i <= keta - 1 ; i++) {
			for (int d = 1 ; d <= 9 ; d++) {
				count += dp[i][d];
			}
		}
		for (int d = 1 ; d <= (snum.charAt(0) - '0') - 1 ; d++) {
			count += dp[keta][d];
		}


		boolean isok = true;
		for (int l = keta - 1 ; l >= 1 ; l--) {
			int dig = snum.charAt(keta - l) - '0';
			int digp = snum.charAt(keta - l - 1) - '0';
			for (int d = 0 ; d < dig ; d++) {
				if (Math.abs(d - digp) >= 2) {
					count += dp[l][d];
				}
			}
			if (Math.abs(dig - digp) <= 1) {
				isok = false;
				break;
			}
		}
		if (isok) {
			count++;
		}
		return count;
	}

	public int howMany(int low, int high) {
		for (int i = 0 ; i <= 9 ; i++) {
			dp[1][i] = 1;
		}

		for (int d = 2 ; d <= 12 ; d++) {
			for (int i = 0 ; i <= 9 ; i++) {
				for (int j = 0 ; j <= 9 ; j++) {
					if (Math.abs(i - j) >= 2) {
						dp[d][i] += dp[d-1][j];
					}
				}
			}
		}
		long ans = count(high) - count(low-1);
		return (int) ans;
	}
}