AtCoder Regular Contest 084 D - Small Multiple

AtCoder ARC ARC #084 問題記録

http://arc084.contest.atcoder.jp/tasks/arc084_b

問題概要

正整数Kのある正の倍数を10進法で表したときの各桁の和の最小値を求めよ。

2 <= K <= 105

解法

以下のようなグラフを考え、最短経路問題を解く。

  • 頂点は0～(K-1)のK個
  • 頂点x → 頂点(x+1)%K にコスト1の辺が出る
  • 頂点x → 頂点(x×10)%K にコスト0の辺が出る
  • コスト1を持って頂点1からスタートし、頂点0をゴールとする

K <= 105 よりダイクストラで解いてもO(KlogK)で間に合う。

この最短経路問題で解いているのは「mod K が x であるすべての正整数の集合における各桁の和の最小値」である。つまり0～(K-1)の各頂点が「mod K で x である正整数の集合」を表し、頂点1から頂点xまでの最短距離が「各桁の和の最小値」を表す。イメージとしては、「1」という数字からスタートしてその数に＋1するか×10するかの遷移を繰り返している、という感じになる。頂点0が「modKが0であるすべての正整数の集合」、すなわちKの正の倍数ということになるので、頂点0までのコストが解となる。

感想

mod Kで0の集合 = Kの倍数の集合 というの自明に見えるけど、なんか頭の中で結びついてなかったので認識しておきたいですね

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

const int INF = 1 << 29;

void main() {
    auto N = readln.chomp.to!int;

    auto dist = new int[](N);
    dist.fill(INF);

    auto pq = new BinaryHeap!(Array!(Tuple!(int, int)), "a[1] > b[1]");
    pq.insert(tuple(1, 1));

    while (!pq.empty) {
        auto n = pq.front[0];
        auto c = pq.front[1];
        pq.removeFront;
        if (dist[n] <= c) continue;
        dist[n] = c;
        if (dist[(n+1)%N] > c+1) pq.insert(tuple((n+1)%N, c+1));
        if (dist[(n*10)%N] > c) pq.insert(tuple((n*10)%N, c));
    }

    dist[0].writeln;
}