DPまとめコンテスト/S - Digit Sum - 競技プログラミング用 知識集積所【7/20更新】

---

問題

DP-S

必要知識

ABCのB以下レベルの内容は省略

• 動的計画法

考え方

例えば、以下のように考える。
入力例としてk=365でd=4の場合を考える。

まず、0以上0未満の場合の各桁の和の値を数えておく。

%dの値	0	1	2	3
個数	0	0	0	0

現状の総和=0

先頭1桁を見て、0以上3未満の数の桁数カウントを考える。
これは、

• 表にある既存の値に0から9をそれぞれくっつける
• 1つ前の桁まで一致しているものに、0,1,2をくっつける

でできる。
もともと%dの値が0だったところには、0をくっつければ%dの値は0%d、1をくっつければ%dの値は1%d、……、9をくっつければ%dの値は9%d
もともと%dの値が1だったところには、0をくっつければ%dの値は1%d、1をくっつければ%dの値は2%d、……、9をくっつければ%dの値は10%d
以下略、というのをまずは処理。

%dの値	0	1	2	3
個数	0	0	0	0

そして、現状の総和だった0を参考に、0から2までをくっつけたときの総和分を足す。

%dの値	0	1	2	3
個数	1	1	1	0

現状の総和=3

先頭2桁を見て、0以上36未満の数の桁数カウントを考える。
これは同じく、

• 表にある既存の値に0から9をそれぞれくっつける
• 1つ前の桁まで一致しているものに、0,1,2,3,4,5をくっつける

でできる。
もともと%dの値が0だったところには、0をくっつければ%dの値は0%d、1をくっつければ%dの値は1%d、……、9をくっつければ%dの値は9%d
もともと%dの値が1だったところには、0をくっつければ%dの値は1%d、1をくっつければ%dの値は2%d、……、9をくっつければ%dの値は10%d
以下略、というのをまずは処理。

%dの値	0	1	2	3
個数	7	8	8	7

そして、現状の総和だった3を参考に、0から5までをくっつけたときの総和分を足す。

%dの値	0	1	2	3
個数	9	9	9	9

現状の総和=9

先頭3桁を見て、0以上365未満の数の桁数カウントを考える。
同様に、まず、

%dの値	0	1	2	3
個数	90	90	90	90

そして、現状の総和だった9を参考に、0から4までをくっつけたときの総和分を足す。

%dの値	0	1	2	3
個数	91	92	91	91

現状の総和=14

これで、0以上365未満のパターンができる。
問題は1以上365以下なので、0に該当するところを1つ減らし、365に該当するところ（現状の総和を見ればよい）を1増やす。

%dの値	0	1	2	3
個数	90	92	92	91

解答はこれの.at(0)の値である。

解答例

解答例

注意点

別解