緑コーダーによる、AtCoder Beginner Contest 155 E - Paymentの解説

ACしたらビビるくらいのパフォーマンスが出た

問題の概要

E - Payment
（要約）通貨は$1,10,100,...,10^n$ の紙幣しかありません。ある価格に対して、払うお札の枚数と、もらうお釣りの枚数の合計の最小値を計算してください。

まず考えたこと

制約が $|N|=10^6$ なので計算量 $O(|N|)$ でないと間に合わないと考えました。サンプルケースから考えて、次のように計算の順序を考えました。

1. 下の桁から計算を行う（後述する桁上がりを考慮するため）
2. その桁の数によって次の2つに分岐する（その桁の数を $d$ とする）
   3. $d\leq5$ なら、そのまま払う方がお釣りをもらうより枚数が少ないので、答えに $d$ を足す。(5は同数ですがこちらに入れる)
   4. $d\geq6$ なら、お釣りをもらう方が枚数が少ないので、答えに $10 - d$ を足す。お釣りをもらうために次の桁に $1$ を足す（桁上がり）。
3. 最後の桁で桁上がりが起きた場合、答えに $1$ を足す。

このようにして記述したコードがこちらになります。

int main(void)
{
    string s; cin >> s;
    int sl = s.size();
    ll ans = 0;
    bool keta = false;
    for(int i = sl-1; i >= 0; i--) { // ルール1
        int d = s[i] - '0';
        if (keta) d++; // 桁上がり
        keta = false;
        if (d > 5) {  // ルール2-2
            ans += 10 - d;
            keta = true;
        }
        else ans += d; // ルール2-1
    }
    if (keta) ans++; // ルール3

    cout << ans << '\n';

    return 0;
}

これでサンプル1、2は正解しましたが、3は間違った数が出てきてしまいました。
桁上がりの数を5以上にしたり、連続する9の数に注目したりしましたが、サンプル3の答えが合いませんでした。

5は払う枚数もお釣りをもらう枚数も同じだが…

その桁の数が5の時は払う枚数もお釣りをもらう枚数も同じですが、桁上がりとしたとき、次の桁が1なら払う枚数が1増えるが、次の桁が6だと次の桁のお釣りをもらう枚数が減るということに気づきました。
というわけで、前項の計算順序 （2） を、以下のように変更しました。

1. $d\leq4$ なら、そのまま払う方がお釣りをもらうより枚数が少ないので、答えに $d$ を足す。
2. $d\geq6$ なら、お釣りをもらう方が枚数が少ないので、答えに $10 - d$ を足す。お釣りをもらうために次の桁に $1$ を足す（桁上がり）。
3. $d=5$ の時、次の桁が4以下ならそのまま払う。5以上ならお釣りをもらって桁上がりする。

これに従ってコードを記述し、ACしました。コードは以下のようになりました。（1行しか変わってない）

ABC155e.cpp

int main(void)
{
    string s; cin >> s;
    int sl = s.size();
    ll ans = 0;
    bool keta = false;
    for(int i = sl-1; i >= 0; i--) { // ルール1
        int d = s[i] - '0';
        if (keta) d++; // 桁上がり
        keta = false;
        // ルール2-2,2-3
        if (d > 5 || (d == 5 && i > 0 && s[i-1] - '0' > 4) ) {
            ans += 10 - d;
            keta = true;
        }
        else ans += d; // ルール2-1
    }
    if (keta) ans++; // ルール3

    cout << ans << '\n';

    return 0;
}