AOJ 2305 Beautiful Currency - mayoko’s diary

問題

要素数 n の数列 a が　beautiful であるとは, 1 以上 n-1 以下の任意の i について, a[i+1] % a[i] == 0 となることである。

数列 a のいくつかの数を入れ替えて, a を beautiful にしたい。a[i] の値を b[i] に変更した際のコストは abs(a[i]-b[i])/a[i] で与えられる。数列 a を b に変更した際のコストは上記コストの最大値で与えられる。

数列 a を beautiful にするための最小コストを求めよ。

解法

まず考察ですが, 全ての数を 1 にすれば beautiful になるので, 答えは絶対 1 以下です。つまり, 各 a[i] について, その値は 1 ～ 2*a[i] の範囲のみを考えれば良いですね。

また, 2*10^5 以下の数では約数の数はそれほど多くならなそう(10^5 までだと 128 個が最高)です。とすると, [1, 200000] の範囲で各 i の約数の数の合計はまぁそれほど多くなさそうです。

そこで, 数列 a を反転させて, dp[i][j] = (i 番目を数 j にしたときの最小コスト) というものを考えます。各 j に対して, i+1 番目の要素は a[i] の約数になっていないといけないので, i+1 番目の数の候補は j の約数のみです。

あらかじめ [1, 200000] の約数を求めておけば, これは十分早く動作します。

const int MAXN = 22;
const int MAX = 202000;
double dp[MAXN][MAX];
vi dd[MAX];

vi divs(int n) {
	vi ret;
	for (int i = 1; i*i <= n; i++) {
		if (n%i == 0) {
			ret.push_back(i);
			if (i*i < n) ret.push_back(n / i);
		}
	}
	return ret;
}

int main() {
	for (int i = 1; i < MAX; i++)
		dd[i] = divs(i);
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++)
		cin >> A[i];
	reverse(A.begin(), A.end());
	for (int i = 0; i < N; i++) for (int j = 0; j < MAX; j++)
		dp[i][j] = 1;
	for (int i = 1; i < 2 * A[0]; i++) {
		dp[0][i] = 1.*abs(i - A[0]) / A[0];
	}
	for (int i = 0; i < N-1; i++) {
		for (int j = 1; j < 2 * A[i]; j++) if (dp[i][j] < 1) {
			for (int d : dd[j]) {
				double tmp = max(dp[i][j], 1.*abs(A[i + 1] - d) / A[i + 1]);
				dp[i + 1][d] = min(dp[i + 1][d], tmp);
			}
		}
	}
	double ans = 1;
	for (int i = 0; i < MAX; i++)
		ans = min(ans, dp[N - 1][i]);
	printf("%.10lf\n", ans);
    return 0;
}