https://beta.atcoder.jp/contests/arc084/tasks/arc084_b
解説
https://beta.atcoder.jp/contests/arc084/submissions/1744570
答えの上限はKの桁和であり、答えを全探索する。
答えがansであるとする。
このときの部分問題は「桁和がansであり、Kの倍数である数が存在するか」である。
これをちょっと変えて「桁和がansであり、modKをとると0である数が存在するか」と取れる。
この判定のために、関数fを用意する。
f(int rest, int mo) := 桁和の残りがrestでこれまでのmodKがmoであるときに、rest=0,modK=0の数が作れるか
(=1:作れる,=2:作れない)
この時、f(rest,mo)はi=[0,9]についてf(rest-i,(mo*10+i)%K)のいずれかが1なら1を返し、そうでないなら2を返す。
桁DP的な事をするのだが、上から確定していく桁DPではなく、下に数を追加していく感じでやっていく。
ans=10,K=4ならば、2000と1100は下に数を追加していくならば、特に区別する必要がないという感じで状態をまとめていく。
メモ化をすれば、状態数はO(45K)で間に合う。
あと、ループが発生する可能性があるので注意。
typedef long long ll; #define INF INT_MAX/2 int K; //--------------------------------------------------------------------------------------------------- int memo[45][100000]; int vis[45][100000]; int f(int rest, int mo) { if (rest == 0 and mo == 0) return 1; if (0 < memo[rest][mo]) return memo[rest][mo]; if (vis[rest][mo]) return memo[rest][mo] = 2; vis[rest][mo] = 1; int res = 2; rep(i, 0, 10) if (0 <= rest - i) { if (f(rest - i, (mo * 10 + i) % K) == 1) { res = 1; break; } } return memo[rest][mo] = res; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> K; int ma = 0, k = K; while (0 < k) { ma += k % 10; k /= 10; } rep(ans, 1, ma) if (f(ans, 0) == 1) { printf("%d\n", ans); return; } printf("%d\n", ma); }