AtCoder Regular Contest 062 C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report
ICPCアジア地区予選のため、つくばのホテルで解いた。
problem
$a_i, b_i$ for $i \lt n$が与えられる。 $a_id_i \le a_{i+1}d_{i+1} \land b_id_i \le b_{i+1}d_{i+1}$を満たす列を$d_i$ for $i \lt n$としたとき、$a_{n-1}d_{n-1} + b_{n-1}d_{n-1}$の最小値を答えよ。
solution
再帰的に$d_i$を計算すればよい。$O(N)$。
式は以下。
- $d_0 = 1$
- $d_{i+1} = \min \{ d \mid a_id_i \le a_{i+1}d \land b_id_i \le b_{i+1}d \}$
$d$を$0$からincrementしていくと間に合わないが、$a_id_i \le a_{i+1}d$を変形して$\frac{a_id_i}{a_{i+1}} \le d$であることを使えば各stepを$O(1)$で行える。
implementation
#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
int main() {
int n; cin >> n;
vector<int> as(n), bs(n); repeat (i,n) cin >> as[i] >> bs[i];
ll a = as[0];
ll b = bs[0];
repeat_from (i,1,n) {
ll d = max(a / as[i], b / bs[i]);
while (not (a <= as[i] * d and b <= bs[i] * d)) d += 1;
a = as[i] * d;
b = bs[i] * d;
}
cout << a + b << endl;
return 0;
}