学習の栞

学びたいことと、学ぶべきことと、学べることの区別がついてない人間の進捗管理

ARC084 D : Small Multiple 解説(お気持ちだけ)

はじめに

AtCoder公式の解説が天才の解法だったので,凡人の解法を書いておく.ふわっとした解法のお気持ちだけ書いておく.はじめに言っておくが,詳解というよりは考察メモに近い.

正確に言葉に表すのが難しい解法なのでお気持ち解説と思ってゆるして.

解法

グラフ作ってダイクストラをやる.

考察

筆算をしてみると,K*m の下位 i桁目は,mの下位i桁で決まることがわかる.筆算は逐次計算することができて,それを踏まえた筆算をやってみると下図の赤字で書いた部分を状態に持ってDPをやりたい衝動に襲われる.

f:id:konjo_p:20171107003633j:plain

さらに状態遷移を考えてみると,下図のような状態遷移でグラフを作れることがわかり,0から出発してまた0に戻ってくるまでの最短経路が答えになることがわかる.

f:id:konjo_p:20171107003615j:plain

コーディングすると通るので書く.

#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>

using namespace std;

#define fi first
#define se second
#define rep(i,n) for(ll i=0; i < (n); ++i)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int dist[100010];
const int INF = 100;

int main() {
	ll K;
	cin >> K;
	rep(i,100010) dist[i] = INF;

	bool src = true;
	priority_queue<pii> q;
	q.push(pii(0,0));
	while(q.size()) {
		pii a = q.top(); q.pop();
		a.fi = -a.fi;
		if(a.fi > dist[a.se])
			continue;

		for(int i = src ? 1 : 0; i < 10; i++) {
			int nex_stat = (a.se + i*K)/10;
			int weight   = (a.se + i*K)%10;
			if(dist[nex_stat] > a.fi + weight) {
				dist[nex_stat] = a.fi + weight;
				q.push(pii(-dist[nex_stat], nex_stat));
			}
		}
		src = false;
	}

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