正整数Kのある正の倍数を10進法で表したときの各桁の和の最小値を求めよ。以下のようなグラフを考え、最短経路問題を解く。ダイクストラで解いてもO(KlogK)で間に合う。あるすべての正整数の集合における各桁の和の最小値」である。ある正整数の集合」を表し、頂点1から頂点xまでの最短距離が「各桁の和の最小値」を表す。イメージとしては、「1」という数字からスタートしてその数に+1するか×10するかの遷移を繰り返している、という感じになる。頂点0が「modKが0であるすべての正整数の集合」、すなわちKの正の倍数ということになるので、頂点0までのコストが解となる。(1)はてなブログをはじめよう!fluffyowlさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。