第2回 ドワンゴからの挑戦状 本選 A - 通勤
解法
考察です。
- ニコニコ数は 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; }