AOJ 2305 Beautiful Currency
問題
KM国には $n$ 種類の効果があり，それぞれの価値は $a[i]$ 円です． さて，それを改正して $b[i]$ にすることになりました． $b[i]$ の美しさは $\max{ |a[i]-b[i]| / a[i] }$ で決まり，小さいほど美しいとします． もっとも美しい組み合わせの美しさを求めてください．
方針
$dp[i][j] = i$ 番目の硬化を $j$ 番目にするときの美しさの最小値． $dp[i][j]$ から $dp[i][k]$ ($k$ は $i$ の倍数) に遷移する． $k$ はあんまり大きくしても無駄なので適当な値 $K$ で打ち切る． すると，計算量は $n \times (K/1 + K/2 + \cdots + K/K)$ になる． この形の分数の列は調和数列と言って $K \log K$ で抑えられるので計算量は $O(n K \log K)$． $K$ はいくつまで必要なのか分からないが 150000 で間に合った．
実装
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
using namespace std;
#define all(c) begin(c), end(c)
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
using ll = long long;
using pii = pair<int, int>;
#define VV(T) vector<vector< T > >
int n;
int a[25];
double dp[25][150000];
double inf = 1e9;
int main() {
while (cin >> n) {
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
fill((double*)begin(dp), (double*)end(dp), inf);
dp[0][1] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 1; j < 150000; ++j) {
for (int k = j; k < 150000; k += j) {
double nxt = dp[i][j];
nxt = max(nxt, abs((double)(a[i] - k) / a[i]));
dp[i + 1][k] = min(dp[i + 1][k], nxt);
}
}
}
printf("%.10lf\n", *min_element(begin(dp[n]), end(dp[n])));
}
}