C++で解く:デジタル時計の数字列を0にする最小操作回数を求めるアルゴリズム

問題概要

n桁の数字列 S があるとします。この S はデジタル時計を表しており、文字列全体で 0 から 10ⁿ − 1 までの整数を表示しています。桁数が足りない場合は、先頭に 0 が並んで表示されるものとします。行える操作は次の2種類です。

• 時計の表示する数値を 1 減らす

• 任意の2つの桁を入れ替える(スワップする)

できるだけ少ない操作回数で、時計の表示を 0 にしたいと考えています。そのために必要な最小の操作回数を求めましょう。

たとえば、入力が S = "1000" の場合、出力は 2 になります。先頭の 1 と末尾の 0 を入れ替えて "0001" にし、続けて 1 減らす操作を行えば "0000" にできるためです。

アプローチ

「1 減らす」操作では、繰り下がりが発生しても、実際に値が変化するのは最も右側にある 0 以外の桁だけです。そのため、末尾以外の位置にある 0 以外の各桁は、スワップで末尾へ移動させてから 0 まで減らすのが最適な戦略になります。

この性質を利用すると、答えは次の要素の合計として求められます。

• 全桁の数字の合計値:各桁を 0 にするために必要な「1 減らす」操作の回数
• 末尾以外にある 0 以外の桁の個数:各桁を末尾へ移動させるために必要なスワップの回数(1桁につき1回)

手順

以下の手順に従って解くことができます。

n := S の長さ
x := S の末尾の桁の値
i を 0 から n−2 まで 1 ずつ増やしながら繰り返す:
    もし S[i] が '0' でなければ:
        x := x + (S[i] の数値) + 1
x を返す

C++実装例

理解を深めるために、次の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int solve(string S) {
    int n = S.size();
    int x = S[n - 1] - '0';
    for (int i = 0; i <= n - 2; i++)
        if (S[i] != '0')
            x = x + S[i] + 1 - '0';
    return x;
}
int main() {
    string S = "1000";
    cout << solve(S) << endl;
}

入力

"1000"

出力

2

計算量

文字列を一度走査するだけなので、時間計算量は O(n)、追加の記憶領域をほとんど使わないため空間計算量は O(1) となります。非常に効率的な解法です。