AtCoder Regular Contest 062 C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

,

https://beta.atcoder.jp/contests/arc062/tasks/arc062_a

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;
}