はまやんはまやんはまやん

hamayanhamayan's blog

Small Multiple [AtCoder Regular Contest 084 D]

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);
}