TopCoder - 暇つぶし2ch

TopCoder at TECH

224:デフォルトの名無しさん
07/10/11 00:29:40
>>222
まず、0以上n以下の整数で、十進法で表したときの和がtargetになるようなやつが何個あるか数える。
これは普通に再帰でできる。たとえば、12345678以下の和が10になるような数を数えたければ、
一の位の数で分類して、
count(12345678,10)
= count(1234567,10) // 1の位が0の場合
+ count(1234567,9) // 1の位が1の場合
+ …
+ count(1234567,2) // 1の位が8の場合
+ count(1234566,1) // 1の位が9の場合
とかでいい。

後は簡単。rangeLowとrangeHighの間で、和がxになるようなやつはいくつあるか、上の関数で数えられるから、
「和がaのうちb番目に小さいものが答え」みたいなことが分かる。
それはcount(x,a)==bとなるように調節すればいい。二分探索。

次ページ

続きを表示

1を表示