ARC084 D : Small Multiple(700)
作成日：2017.11.05
最終更新日：2017.11.05
問題概要
$K$の正の倍数の10進法での各桁の和としてあり得る最小の値を求めよ。
制約
$1 \leq K \leq 10^5$
考え方
$K$の倍数だけを見て考えるのは難しいので、正の整数全体で考える。
但し、考えるべき状態の種類を減らすために$mod \: K$で等しいものは同一視する。
各桁の和を考えるから、桁を1つずつ増やすことにする。
これは元の整数を$10$倍して$0$から$9$のいずれかを足すことで桁数に関係なく達成できる。
言い換えると、各整数からの遷移は10種類だけであることが分かる。
以上より整数を頂点、遷移を辺としてみると、頂点が$K$個、辺が$10K$本の有向グラフが構築できる。
さらに辺のコストを新たに増やした桁の数字とすれば、最短経路問題に帰着できる。
この条件ではダイクストラ法で十分高速である。
ソースコード
マクロ等はこちら
const int MC = 100010;
int K;
int d[MC];
priority_queue<P2 , vector<P2> , greater<P2> > Q;
int main(){
cin >> K;
fill(d,d+MC,123456789);
repm(i,9,0){
d[i%K] = i;
Q.push(MP(d[i%K],i%K));
}
while(!Q.empty()){
int x = Q.top().second;
Q.pop();
repp(i,0,10){
int y = (x*10+i)%K;
if(d[y] > d[x]+i){
d[y] = d[x]+i;
Q.push(MP(d[y],y));
}
}
}
cout << d[0] << endl;
return 0;
}解法まとめ
頂点$i$に$mod \: K$で$i$と等しい正の整数の集合を割り当て、頂点$i$から頂点$10i+j$($0$$\leq j$$\leq 9$,$mod \: K$)にコスト$j$の有向辺を張ったグラフを考える。
頂点$v$($1 \leq v \leq 9$)への到達コストの初期値を$v$とし、ダイクストラ法で頂点$0$への到達コストを求める。(9-24行)