第2回 ドワンゴからの挑戦状 本選 A - 通勤

問題

dwango2016-honsen.contest.atcoder.jp

解法

考察です。

• ニコニコ数は 18*2 = 36 個程度しかない
• L, x*L, ... とか言うように L を小さい順に並べるのではなく, つかう L の数を大きい順に並べていくと考えると, 「大きい数から貪欲に使っていく」という方針が正しいことが言える(使った数を L[0], L[1], ... とすると, L[i+1] は L[i] の倍数になっていることから言える)

これをプログラム的に考えると, 例えば N = 31 では,
31 -> (ニコ数 2 を使うことを考えると 31%2 = 1 回は 2 の倍数で処理出来ないので飛行する。31/2 = 15 の分はあとで考える) -> 15 -> (ニコ数 5 を使うことを考えると 15/5 = 3 の分残る) -> 3 -> (ニコ数 2 を使うと 1 回分は処理できないので飛行する。 3/2 = 1 だけ残る) -> 1(これは 1 回の飛行で処理する)
で, 合計 1+1+1 = 3 回です。

これを逆順に考えると, 0 -> 1 -> 11 -> 31 となります。
最初の 1 は, 31 を 2 で割った余り, そのあと 10 増えてるのは, 5 で割ったあと 3 を 2 で割った時余った余りの 1 の分, そのあと 20 増えてるのは 5 で割って 2 で割ったあと残った 1 の分です。

map<ll, ll> dp;
const ll INF = 1ll<<60;

void dfs(string s, ll N, vector<ll>& num) {
    if (s.empty()) {
        dfs("2", N, num);
        dfs("5", N, num);
    } else {
        ll now = stoll(s);
        if (now > N) return;
        num.push_back(now);
        if (s.back() == '2') dfs(s+"5", N, num);
        else dfs(s+"2", N, num);
    }
}

ll solve(ll N, const vector<ll>& num) {
    auto it = dp.find(N);
    if (it != dp.end()) return (it->second);
    ll ret = INF;
    for (ll el : num) {
        if (el > N) continue;
        ret = min(ret, solve(N/el, num) + N%el);
    }
    return dp[N] = ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    vector<ll> num;
    {
        string s;
        dfs(s, N, num);
    }
    dp[0] = 0;
    dp[1] = 1;
    cout << solve(N, num) << endl;
    return 0;
}