2021-07-30

AtCoder ABC 077 D - Small Multiple (ARC 084 D) (橙色, 700 点)

これほどシンプルな問題がグラフ最短路問題になるのは感動的ですね！

問題へのリンク

問題概要

$K$ の正の倍数をすべて考えたときの、各桁の和として考えられる最小値を求めてください。

制約

$2 \le K \le 10^{5}$

うまく数字を並べるゲームと捉える

$K$ の倍数をひたすら試す方法をまず考えたくなるものの、桁和が最小を達成する値がとても大きくなることがあります。たとえば $K = 65535 (= 2^{16})$ のとき、 $65536 \times 5^{16} = 10000000000000000$ が最適解となります。この解を探索で見出すことは難しいです。

そこで視点を変えて、「 $K$ の倍数のうち桁数が小さいものを探す」のではなく、次のような問題を解くものと考えてみましょう。

"12003212..." のように、数字を並べて行ったときに、その数字の和がなるべく小さくなるようにしつつ、 $K$ で割ったあまりがちょうど 0 となるようにせよ

このように考えると、作られる整数たちを $K$ で割ったあまりで分類したくなります。次のような動的計画法を考えるイメージです。

dp[r] ← あまりが $r$ になるような数字の作り方のうちの、各桁の和の最小値

数字を並べる操作をグラフで捉える

次に、上記の dp の遷移を詰めるために「具体的に整数をどのようにつくるか」を考えてみましょう。一般に整数は

「+1」する
「× 10」する

という 2 つの手続きによって、作り上げていくことができます。この考え方自体は、競プロ典型90問の問 5 でも部分的に登場する典型テクニックです。

atcoder.jp

たとえば "4649" という整数は次のような手順で作ることができます。

1 という整数からスタートする
「+1」を繰り返すことで 4 にする
「× 10」することで 40 にする
「+1」を繰り返すことで 46 にする
「× 10」することで 460 にする
「+1」を繰り返すことで 464 にする
「× 10」することで 4640 にする
「+1」を繰り返すことで 4649 にする

「+1」の操作は整数の桁和を 1 増やす操作であり、「×10」の操作は整数の桁和を変えない操作であることに注意しましょう。ここで、次のようなグラフを考えてみましょう。

[頂点集合]： $K$ で割ったあまりが $0, 1, \dots, K-1$ であることを表す $K$ 個の頂点 (あまりが $r$ であることを表す頂点を、頂点 $r$ と呼ぶことにします)
[辺集合]：頂点に対して、次の 2 本の辺を貼ります
- 頂点 $r + 1 ({\rm mod}. K)$ に対して、コスト 1 の辺
- 頂点 $10r ({\rm mod}. K)$ に対して、コスト 0 の辺

このようなグラフ上で、頂点 1 (1 という整数に対応) から出発して、頂点 0 ( $K$ で割ったあまりが 0 になる整数に対応) に到達するまでの、最短経路長を求めましょう。これが求めたい「桁和の最小値」に対応します！！！

一つの懸念は、「+1」という操作のコストを一律に 1 としていることです。実際には、たとえば 4649 という整数に「+1」を施すと 4650 となり、桁和はむしろかならず減少します。しかしながら 4650 を作るときには、4649 に「+1」をするよりも、465 を作ってから「× 10」をする方がかならずコストが小さくなることに注意しましょう。よって、4649 に「+1」する操作のコストは 1 であるとして扱っても問題ないことが言えます。以上のことは 4649 という整数に限らず、一般に言えます。

0-1 BFS

以上より、頂点数 $K$ 、辺数が $2K$ のグラフ上の最短路を求める問題へと帰着されました。辺の重みが 0, 1 のみですので 0-1 BFS を用いることで計算量は $O(K)$ となります。

なお 0-1 BFS については、次の問題で解説しています。

drken1215.hatenablog.com

コード

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 無限大を表す値
const int INF = 1<<29;

int main() {
    // 入力
    int K;
    cin >> K;

    // 距離配列と deque
    vector<int> dist(K, INF);
    deque<int> que;

    // 初期値として 1 を挿入
    dist[1] = 1;
    que.push_front(1);

    // 0-1 BFS
    while (!que.empty()) {
        // deque の先頭要素を取り出す
        int v = que.front();
        que.pop_front();

        // 「×10」を試す
        // コスト 0 なので deque の先頭に push
        int v2 = (v * 10) % K;
        if (dist[v2] > dist[v]) {
            dist[v2] = dist[v];
            que.push_front(v2);
        }

        // 「+1」を試す
        // コスト 1 なので deque の末尾に push
        v2 = (v + 1) % K;
        if (dist[v2] > dist[v] + 1) {
            dist[v2] = dist[v] + 1;
            que.push_back(v2);
        }
    }

    cout << dist[0] << endl;
}