AtCoder ARC #084 : D - Small Multiple

これは700ptだけどすんなり解けた。
https://beta.atcoder.jp/contests/arc084/tasks/arc084_b

問題

正整数Kが与えられる。
Kの倍数のうち、10進数表記で各桁の和は最小いくつになるか。

解法

以下の状態を考え、f(0)～f(K-1)についてダイクストラの要領で求めていく。
f(x) := Kで割った余りがxのうち、各桁の総和の最小値

状態遷移としては、f(x)がわかっているとき、それを10倍して1の位を0～9とするケースを考えよう。
1の位をyとすると、f((10x+y)%K) = f(x) + yで状態を更新できる。

あとはf(0)を答えるだけ。

int K;
int mi[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K;
	FOR(i,K) mi[i]=1<<30;
	priority_queue<pair<int,int>> P;
	for(i=1;i<=9;i++) {
		mi[i%K]=min(mi[i%K],i);
		P.push({-mi[i%K],i%K});
	}
	
	while(P.size()) {
		int cur=P.top().second;
		int cost=-P.top().first;
		P.pop();
		if(cost!=mi[cur]) continue;
		FOR(i,10) {
			int nc=cost+i;
			int nex=(cur*10+i)%K;
			if(mi[nex]>nc) {
				mi[nex]=nc;
				P.push({-mi[nex],nex});
			}
		}
	}
	
	cout<<mi[0]<<endl;
	
	
}

まとめ

500-600pt位な気はする。