【AtCoder】ABC 407 C - Security 2 | 緑コーダーが解くAtCoder

atcoder.jp

配点: 300 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 295 / NoviSteps: 3Q

問題概要

文字列を1つ表示する画面と2つのボタンからなる装置がある。

画面に表示される文字列を とする。 ははじめ空文字列であり、ボタンを押すことで に以下の変化が起こる。

• ボタン A を押すと、 の末尾に0が追加される。
• ボタン B を押すと、 に含まれるすべての数字がそれぞれ次の数字に置き換わる。ここで、9の次の数字は0とする。

文字列 が与えられるので、 が空文字列である状態から を に一致させるとき、ボタンを最少で何回押す必要があるかを求めよ。

制約

• 

考察

操作を繰り返してある文字列を別の文字列に一致させるような問題は、逆から考えると分かりやすい場合がある。

今回は、 を逆順にしたときの1桁目から順に にすることを考える。

サンプルケース2 : を例にとると、これを反転した新たな は となる。

• 1桁目 を にする。このときの操作回数は 回である。
• 2桁目 は、 回の操作を経て になった。ここから にするための操作回数は 回である。
• 3桁目 は、 回の操作を経て になった。ここから にするための操作回数は である。

を削除する操作の回数も含めると、このケースの答えは である。

これをアルゴリズムに落とし込むと以下のようになる。なお、 は既に反転されているものとする。

---

1. 答えのカウンターと、ボタン B を押した回数 を で初期化する。
2. 各 について、以下を行う。
   1. とする。ここで、 は負になることもあり得る。
   2. 答えのカウンターに、 を加える( になった桁をボタン A で削除する操作も含めている)。
   3. を だけ増やす。

---

実装時は、負の数に対する剰余処理に注意しよう。実装例のmod関数を参考に。

実装例

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

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <class T1, class T2>
inline auto mod(T1 x, T2 r) { return (x % r + r) % r; }

// ======================================== //

int main()
{
    string S;
    cin >> S;

    int l = S.size();
    reverse(all(S));

    int ans = 0;
    int b = 0;
    rep(i, 0, l)
    {
        int d = S[i] - '0';
        d = mod(d - b, 10);

        ans += d + 1;
        b += d;
    }

    cout << ans << endl;

    return 0;
}

atcoder.jp

実装時間: 15分

コメント

解法は割とすぐ思いついたのだが、コードに落とし込むのに時間がかかってしまった。

最近のABCのC問題は、「このデータ構造・アルゴリズムで解ける！」のように典型的な問題ではなくて、少々の考察を要する ad hoc なものが多いように感じる。