ARC123 C - 1, 2, 3 - Decomposition (600)
nをk分割で作れるかをkの昇順でメモ化再帰で求めていく
手元で試すと
$ k=5
くらいで全部できたのでおそらくこれで十分
以下の順で求める
nの一番下の桁をvとする
$ k \le v \le 3k
になるように上の位から繰り下げてvに10を足す
これができないなら作れない
繰り下がりを処理した後、
$ n/10
を
$ 1,2,\cdots k
で分割できるかを計算する
いずれかで作れればこれも作れる
それ以外は作れない
問題:
https://atcoder.jp/contests/arc123/tasks/arc123_c
提出:
https://atcoder.jp/contests/arc123/submissions/24366460
#ARC123
#600pt
#C
#ARC
#AtCoder