連続する整数の各桁の数字の和
締め切りが 2017/01/24 10:00 AM なので，その 1 分後に投稿されるように予約
設問
a, b という2つの正の整数が与えられたとき、aからbまでの連続する整数について、各桁の数字の和を求めることを考えます。
例えば、a = 7, b = 16のとき、7, 8, 9, 10, 11, 12, 13, 14, 15, 16の各桁の数字を足して、
7 + 8 + 9 + 1 + 0 + 1 + 1 + 1 + 2 + 1 + 3 + 1 + 4 + 1 + 5 + 1 + 6 = 52
となります。
また、a = 12, b = 19のときは、
1 + 2 + 1 + 3 + 1 + 4 + 1 + 5 + 1 + 6 + 1 + 7 + 1 + 8 + 1 + 9 = 52
となり、同じ値になります。
このように、同じ値が得られる正の整数 a, b のペアは一つとは限りません。
標準入力から a, b の値がスペースで区切って与えられたとき、与えられた a, b の範囲に重なる（両端を含む）ようなペアがいくつあるかを求め、標準出力に出力してください。
（a = 21, b = 28 なども同じ値になりますが、7〜16 と 21〜28は重なる範囲がないため対象外です。）
例えば、上記の a = 7, b = 16 の場合、a = 12, b = 19 の他にも a = 3, b = 13 の場合があり、合わせて2通りですので、以下のように出力します。
【入出力サンプル】
標準入力
7 16
標準出力
2
※a, b は32ビット整数の範囲で、0 < b - a < 2500 を満たす数が与えられるものとします。
========================================================================================
R で書くと実行時間制限にかかるので，Java に書き直して O.K.
ただ，Java だと，処理系によりメモリーオーバーになるので小細工が必要になる
R によるプログラム
f = function(a, b, range=8000) {
if (b-a < 1000) {
max = b+2*(b-a)
min = 2
} else {
max = b+range
min = a-range
}
x = integer(max)
x[min-1] = sum(as.numeric(unlist(strsplit(as.character(min-1), ""))))
for (i in min:max) {
x[i] = x[i-1]+sum(as.numeric(unlist(strsplit(as.character(i), ""))))
}
s = x[b]-x[a-1]
count = 0
for (i in a:(b-1)) {
for (j in min:a) {
if (x[i]-x[j-1] == s) {
count = count+1
}
}
}
for (i in (a+1):b) {
for (j in i:max) {
if (x[j]-x[i-1] == s) {
count = count+1
}
}
}
count
}
f(7, 16) # 2
f(100, 150) # 15
f(2000, 2017) # 3
f(12345678, 12347654)) # 167
f(123456789, 123459012) # 294
2 つの二重ループを outer 関数に置き換え，制約範囲を限ると，テストシステムでも 1 秒以内に収まった（テストデータをクリアーするということに限る。一般解ではない）。
f = function(a, b, range=2500) {
if (b-a < 1000) {
max = b+2*(b-a)
min = 2
} else {
max = b+range
min = a-range
}
x = integer(max)
x[min-1] = sum(as.integer(strsplit(as.character(min-1), "")[[1]]))
for (i in min:max) {
x[i] = x[i-1]+sum(as.integer(strsplit(as.character(i), "")[[1]]))
}
s = x[b]-x[a-1]
res1 = outer(x[a:(b-1)], x[min:a-1], "-")
res2 = outer(x[b:max], x[(a+1):b-1], "-")
sum(res1 == s)+sum(res2 == s)
}
========================================================================================
Java によるプログラム
import java.util.*;
import java.util.regex.*;
class Main {
public static void main(String[] args) {
System.out.println(f(7, 16));
System.out.println(f(100, 150));
System.out.println(f(2000, 2017));
System.out.println(f(12345678, 12347654));
System.out.println(f(123456789, 123459012));
}
static int digitsSum(int n) {
int sum = 0;
while (n != 0) {
sum += n%10;
n /= 10;
}
return sum;
}
static int f(int a, int b) {
int max, min, i, j, s, count = 0;
int range = 8000;
if (b-a < 1000) {
max = b+2*(b-a);
min = 2;
} else {
max = b+range;
min = a-range;
}
int [] x = new int[max-min+3];
x[1] = digitsSum(min-1);
for (i = min; max >= i; i++) {
x[i-min+2] = x[i-1-min+2]+digitsSum(i);
}
s = x[b-min+2]-x[a-1-min+2];
count = 0;
for (i = a-min+2; b-1-min+2 >= i; i++) {
for (j = min-min+2; a-min+2 >= j; j++) {
if (x[i]-x[j-1] == s) {
count++;
}
}
}
for (i = a+1-min+2; b-min+2 >= i; i++) {
for (j = i; max-min+2 >= j; j++) {
if (x[j]-x[i-1] == s) {
count++;
}
}
}
return count;
}
}
