Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-30SRM300台を練習していく part6

SRM 311 SumThemAll

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

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

(mediumにしては)簡単。

digitsの合計を表すテーブルを1000000まで持っておき、

lowerBoundとupperBoundを1000000で割った商と余りに分けてそれぞれ計算する。


public class SumThemAll {

	public long getSum(int lowerBound, int upperBound) {
		long[] dp = new long[1000001];
		long[] basesum = new long[1000001];
		for (int i = 1 ; i <= 9 ; i++) {
			dp[i] = i;
		}
		for (int i = 10 ; i <= 99 ; i++) {
			dp[i] = dp[i/10] + dp[i%10];
		}
		for (int i = 100 ; i <= 9999 ; i++) {
			dp[i] = dp[i/100] + dp[i%100];
		}
		for (int i = 10000 ; i <= 1000000 ; i++) {
			dp[i] = dp[i/10000] + dp[i%10000];
		}
		for (int i = 1 ; i <= 1000000 ; i++ ) {
			basesum[i] = basesum[i-1] + dp[i];
		}


		long ans = 0;
		if (upperBound <= 1000000) {
			return basesum[upperBound] - ((lowerBound == 0) ? 0 : basesum[lowerBound-1]);
		}

		long meta_a = lowerBound / 1000000;
		long meta_b = upperBound / 1000000;
		if (meta_a < meta_b) {
			long tmp_a = 0;
			if (lowerBound % 1000000 == 0) {
				tmp_a = basesum[999999];
			} else {
				tmp_a = basesum[999999] - basesum[lowerBound % 1000000 - 1];
			}
			ans += tmp_a + dp[(int)meta_a] * (1000000 - lowerBound % 1000000);

			for (long i = meta_a + 1 ; i < meta_b ; i++) {
				ans += basesum[999999] + dp[(int)i] * 1000000;
			}
			long tmp_b = basesum[upperBound % 1000000];
			ans += tmp_b + dp[(int)meta_b] * (upperBound % 1000000 + 1);
		} else {
			ans += dp[(int)meta_a] * (upperBound % 1000000 - lowerBound % 1000000 + 1);
			ans += basesum[upperBound % 1000000];
			if (lowerBound % 1000000 != 0) {
				ans -= basesum[lowerBound % 1000000 - 1];
			}
		}
		return ans;
	}
}