裏紙

ほぼ競プロ、たまに日記

GCJ 2017 R1A B - Ratatouille

GCJ programming

問題

Dashboard - Round 1A 2017 - Google Code Jam

問題概要

究極のラタテュイユのレシピが完成した。レシピにはどの原料をどれほど使うべきか、が記されている。ラタテュイユにはn種類の原料が必要であり、1人前を作るのにi番目の原料がR_iグラム必要である。

その原料をセットとして揃えて売るために、原料パッケージをいくつか注文することにした。原料パッケージには、ある特定の原料が一定量だけ入っている。各原料ごとにp個のパッケージがあり、i番目の原料のj個目のパッケージにはQ_{ij}グラムの原料が入っている。

これらのパッケージを使って、ラタテュイユキットをなるべく多く作りたい。ラタテュイユキットは、ラタテュイユに必要な各原料のパッケージ1つずつを組み合わせて構成される。

原料の比が厳密なもののみを作ろうとするとあんまりセットが作れないので、実際にそのセットで作ることができるとラベルに書いてある量に対して、原料は90%~110%の間に収まっていれば良いということにした。

例：ラタテュイユ1人前に500gのトマトと300gの玉ねぎが必要な場合

原料パッケージとして、900gのトマトと660gの玉ねぎを持っているとする。
これらのパッケージを使って、2人前のキットを作ることが出来る。
2人前には1000gのトマトと600gの玉ねぎが必要だが、
  トマトの量は1000gの90%~110%
  玉ねぎの量は600gの90%~110%
に収まっていれば良いので、可能である。

また、x人前のキットを作ると考えるときに、xは必ず整数でなければならない。更に、何人前のキットを作ろうと、それは1個のキットと見なす。この時に、作れるキットの個数を最大化せよ。

  • 1 \le n \le 50
  • 1 \le p \le 50
  • n * p \le 1000
  • 1 \le r_i \le 10^6
  • 1 \le q_{ij} \le 10^6

アイデア

パッケージのグラム数は本質的に重要な情報ではなく、重要なことは各パッケージは何人前に割り当てることが出来るのかということである。

例えば、1人前には10gのトマトが必要な時に、201gのトマトのパッケージは19~22人前のキットに入れることが出来る。このように、各パッケージを区間として考えることにしよう。

では、この区間を計算することを考える。パッケージの量をQ、その原料の1人前の量をRとすると、m人前のキットに入れることが出来る時、 0.9 * R * m \le Q \le 1.1 * R * mを満たし、mについて変形すれば \frac{10 * Q}{11 * R} \le m \le \frac{10 * Q}{9 * R}と計算でき、O(1)で計算できる。

さて、この区間を各原料ごとに昇順でソートしておき、各原料について何番目を見ているかを保存しながら、小さい方から貪欲にi人前のセットが作れるかをイテレーションしていくと良い。

任意の区間に対してだとこれが上手く行かない場合があるような感じがするが、今回のような区間の作り方だと上手くいく。なぜなら、今回の区間の作り方に従うと以下のことが成り立つ：

同じ原料の2つの区間l_1とl_2を考える。l_1がl_2に含まれる時、2つの区間は少なくとも1つの区間の端点を共有している(Property 0)。

→ 各区間が実際にS_iグラムから得られたものだったとすると、S_1 \le S_2のとき、l_1の下限はl_2より大きいことはない(つまりl_2と下限が一致)。逆に、S_1 \gt S_2のとき、l_1の上限はl_2より小さいことはない(つまりl_2と上限が一致)。よって少なくとも一方は端点が一致することが分かる。

上の貪欲が正しいことを証明する前に、他にも良い性質があるのでそれを確認しておこう。

  • Property 1: ある区間を捨てる(どのキットにも入れない)ことにする時と言うのはもうその区間のあらゆるx人前のキットが作れないことを意味する。

  • Property 2: ある区間を採用する(あるキットに入れる)ことにする時に、区間の共通部分のうち最小値がMだとすると、M未満のx人前のキットはもう作れない。

確かに、上の貪欲に従っていくなら、2つとも当たり前のことだという感じがする。それでは証明に入る。

上の貪欲によって、M_1 , M_2, \ldots , M_k人前のキットが作成されていったとする。ここで、N_1 , N_2, \ldots , N_k, N_{k+1}人前のキットの作り方のうち最小のものがあるとする。

Case A

iをN_i \lt M_iを満たす最小の値とする。Property 2によって、このようなことが発生するのはN_i人前のキットがもう作れない場合に発生する。これは、考えた貪欲がそのような区間を捨てているか、以前に使用してしまった可能性が考えられるが、前者はProperty 1によって有り得ない。また、貪欲の選び方とProperty 0によって後者も起こり得ない。ある区間rが選ばれる時、その原料パッケージに対してまだ残っている区間はrよりも上限は小さいことはない。よってその時点で選ぶのはrがベターであることが分かる。

Case B

Aのようなiが無いとする。つまり、N_{k+1}のキットが作成できなかったことになるが、Property 0,1によりこれは有り得ないことが同様に言える。

以上より上の貪欲は最適なことが分かる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

using pi = pair<int,int>;

pi make_range(int Q, int R)
{
    int l = 10*Q;
    int d = 11*R;

    int a = (l%d!=0);
    l /= d;
    l += a;
    int r = 10*Q/(9*R);

    if(l>r) return pi(0,0);
    return pi(l,r);
}

int solve()
{
    int n,p;
    cin >>n >>p;
    vector<int> r(n);
    rep(i,n) cin >>r[i];
    vector<vector<pi>> q(n,vector<pi>(p));
    rep(i,n)
    {
        rep(j,p)
        {
            int t;
            cin >>t;
            q[i][j] = make_range(t,r[i]);
        }
        sort(all(q[i]));
    }

    int ans = 0;
    int mul = 1;
    vector<int> idx(n);
    while(1)
    {
        rep(i,n)
        {
            while(idx[i]<p && q[i][idx[i]].se<mul) ++idx[i];
            if(idx[i]==p) return ans;
        }

        bool ok = true;
        rep(i,n)
        {
            ok &= (q[i][idx[i]].fi<=mul && mul<=q[i][idx[i]].se);
        }

        if(ok)
        {
            ++ans;
            rep(i,n) ++idx[i];
        }
        else ++mul;
    }
}

int main()
{
    int T;
    cin >>T;
    rep(t,T) printf("Case #%d: %d\n", t+1, solve());
    return 0;
}