Google Code Jam 2017 Round 1A: B. Ratatouille

,

https://code.google.com/codejam/contest/5304486/dashboard#s=p1

問題文が難しすぎる。嫌い。

problem

$N$種類の食材がそれぞれ$P$パッケージずつあり、それぞれ$Q_{i,j}$グラム含む。 ratatouilleを$1$個作るのには食材$i$がそれぞれ$0.9R_i \sim 1.1R_i$グラム必要である。 $N$種類の食材からそれぞれ$1$パッケージずつ選び、整数$k$を決め、食材を過不足なく使って$k$個のratatouilleを消費すれば、$1$個のkitができる。 作るkitの数を最大化せよ。 ratatouilleの数ではないことに注意。

solution

区間に直して整列して見ていく。$O(NP \log {NP})$。

各$Q_{i,j}$から、$k \in [L, R)$と$k$個のratatouilleを作るのに$Q_{i,j}$を使えることが同値になるように区間$[L_{i,j}, R_{i,j})$を作る。 $L_{i,j}$を食材$i$の追加クエリ、$R_{i,j}$を食材$i$の削除クエリとして見て、これらをその値の順に見ていく。 個数$k$を増やしていきながら処理していって、全ての食材が同時にひとつ以上使えるならば貪欲に使えばよい。

implementation

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
int solve(int n, int p, vector<int> const & required, vector<vector<int> > const & quantity) {
    auto low = vectors(n, p, int());
    auto high = vectors(n, p, int()); // [l, r]
    repeat (i,n) {
        repeat (j,p) {
            const int r = required[i];
            const int q = quantity[i][j];
            int & lo = low[i][j];
            int & hi = high[i][j];
            lo = (10*q + 11*r-1) / (11*r);
            hi = 10*q / ( 9*r);
            if (lo <= hi) {
                constexpr double eps = 1e-8;
                assert (0.9*r*lo < eps + q and q < eps + 1.1*r*lo);
                assert (0.9*r*hi < eps + q and q < eps + 1.1*r*hi);
                assert (not (0.9*r*(lo-1) < eps + q and q < eps + 1.1*r*(lo-1)));
                assert (not (0.9*r*(hi+1) < eps + q and q < eps + 1.1*r*(hi+1)));
            }
        }
    }
    reversed_priority_queue<tuple<int, bool, int> > que;
    repeat (i,n) {
        repeat (j,p) {
            if (low[i][j] <= high[i][j]) {
                que.emplace(low[i][j], false, i);
                que.emplace(high[i][j], true, i);
            }
        }
    }
    vector<int> used(n);
    vector<int> remaining(n);
    int result = 0;
    while (not que.empty()) {
        int cur_time; bool is_pop; int i; tie(cur_time, is_pop, i) = que.top(); que.pop();
        if (is_pop) {
            if (used[i]) {
                -- used[i];
            } else {
                assert (remaining[i]);
                -- remaining[i];
            }
        } else {
            ++ remaining[i];
            if (remaining[i] == 1) {
                if (*whole(min_element, remaining) >= 1) {
                    repeat (j,n) remaining[j] -= 1;
                    repeat (j,n) used[j] += 1;
                    result += 1;
                }
            }
        }
    }
    return result;
}
int main() {
    int t; scanf("%d", &t);
    repeat (x,t) {
        int n, p; scanf("%d%d", &n, &p);
        vector<int> r(n); repeat (i,n) scanf("%d", &r[i]);
        auto q = vectors(n, p, int()); repeat (i,n) repeat (j,p) scanf("%d", &q[i][j]);
        int result = solve(n, p, r, q);
        printf("Case #%d: %d\n", x+1, result);
    }
    return 0;
}