[AtCoder] ABC155 E – Payment (500点)

2020年2月17日2020年9月2日AtCoderDP,500点,桁ごと,お釣り,硬貨

問題へのリンク

問題概要

\(1, 10, 10^2, 10^3, \dots, 10^{(10^{100})}\) の紙幣で金銭のやり取りをする。

N 円払う時、支払うのに使う紙幣の枚数と、お釣りでもらう紙幣の枚数の合計が最小になるような払い方を考え、その値を出力せよ。

制約

• \(1 \leq N \leq 10^{1,000,000}\)

考え方

制約を見ると、Nは64bit では収まりきらない大きな数です。このような時は、桁ごとに考えるのが良いです。

このときに、上位の桁と下位の桁のどちらから考えるかで悩みます。この問題ではお釣りが発生するので、上位の桁の払い方を決定しないと、下位の桁のことを考えにくそうです。

具体的にN=361 の時を考えてみましょう。まず3桁目は以下のどちらかの払い方があります。

• 100円札 3 枚でちょうど支払う
• 100円札 4 枚を支払って下の桁でお釣りをもらう

次に2桁目は、

• 10円札 6 枚でちょうど支払う
• 10円札 7 枚を支払って下の桁でお釣りをもらう
• 上の桁で払い過ぎていたので、10円札 (10-6) 枚のお釣りをもらってちょうど支払う
• 上の桁で払い過ぎていたので、10円札 (10-6 – 1) 枚のお釣りをもらい、下の桁でお釣りをもらう

最後に1桁目は、

• 1円札 1 枚でちょうど支払う
• 上の桁で払い過ぎていたので、1円札 (10-1) 枚のお釣りをもらってちょうど支払う

のような払い方になります。

以上を考えると、i 桁目が a (\(0 \leq a\leq 9\)) だった時は、

1. \(10^i\) 円の紙幣を a 枚使って払う
2. \(10^i\) 円の紙幣を a+1 枚使って、下の桁のために余分に払っておく
3. 上の桁で余分に支払って繰り下がりが発生し、お釣りが\(10^i\) 円の紙幣 10 – a 枚
4. 上の桁で余分に支払って繰り下がりが発生し、下の桁のために余分に払っておくと、お釣りが\(10^i\) 円の紙幣 10 – a -1枚

だけの払い方があります。これは、i+1 桁目までの払い方を用いて、i 桁目の払い方を決定できるので、動的計画法が使えそうです。

解き方

以下のような 動的計画法を考えます。

dp の初期化

• dp[ 0 ][ true ] = 1
• 上以外は全て 0

dp の更新

上から i+1 桁目をピッタリ支払うとき、(dp[ i+1 ][ false ] について)

• dp[ i ][ false ] + N[ i ] (N[ i ] 枚ピッタリで払う)
• dp[ i ][ true ] + (10 – N[ i ]) (上位の桁で余分に支払っていたのでお釣りをもらう)

の最小値。

上から i+1 桁目を余分に支払い下の桁でお釣りをもらう時、(dp[ i+1 ][ true ] について)

• dp[ i ][ false ] + N[ i ] + 1 (1枚余分に支払う)
• dp[ i ][ true ] + (10 – N[ i ] – 1) (上位の桁で余分に支払っていたのでお釣りをもらうが、下の桁のために1枚残しておく)

の最小値。

答え

• dp[ Nの桁数 ][ 0 ]

実装例

C++ での例です。

#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;

string N;
ll dp[1000005][2];
int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);

    cin >> N;

    dp[0][1] = 1;
    REP(i, (int)N.size()) {
        int now = (int)(N[i] - '0');
        dp[i + 1][0] = min(dp[i][0] + now, dp[i][1] + (10 - now));
        dp[i + 1][1] = min(dp[i][0] + now + 1, dp[i][1] + (10 - now - 1));
    }

    cout << dp[N.size()][0] << endl;

    return 0;
}