UTPC 2012 E問題

Tatsuya Yatagawa
Programming Contest

続いてはE問題です。

この問題はなかなかの曲者で、一見「なぁんだ、どうせ二分探索じゃん」と思うのですが、実はそれではうまくいきません。このような議席の割り振り問題ではアラバマのパラドックスという矛盾が起こることが知られてるらしいです。アラバマのパラドックスとは、得票数が変わらなければ総議席数が増えたときに獲得議席数はどの政党も増えるはずという予想に反して、獲得議席が減ることがあるというパラドックスです。

アラバマのパラドックス

だからと言って線形探索ではどう頑張っても間に合わないので、ここでは二分探索である程度あたりをつけて、あとはそこから下へ線形探索していくという方法を取ります。またアラバマのパラドックスが起こるとしても、各政党の獲得議席数は、今わかっている議席数-1よりは少なくとも大きくなることが分かるので、これでさらに計算を早くできます。

余談ですが、他の人のコードを見たところunsigned long longを使わなくてもlong longで票数は収まりきるらしい。unsignedにするために余計な条件分岐がところどころ入っていますが、あまり気にしないでください。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <algorithm>
#include <limits.h>
#include <string.h>
#include <ctype.h>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
using namespace std;

typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int, int> PII;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPD(i,n) for(int i=n; i>=0; i--)

template <typename T> inline T tmax(T t1, T t2) { return t1 > t2 ? t1 : t2; }
template <typename T> inline T tmin(T t1, T t2) { return t1 < t2 ? t1 : t2; }

typedef multimap<double, int, std::greater<double> > MDI;
typedef pair<double, int> PDI;

struct Node {
    ULL r;
    int i;
};

bool operator <(const Node& n1, const Node& n2) {
    return n1.r < n2.r;
}

bool operator >(const Node& n1, const Node& n2) {
    return n1.r > n2.r;
}

int N;
ULL s;
vector<ULL> a, b, c;

bool check(ULL m) {
    bool ok = true;
    ULL rest = m;
    vector<Node> nodes(N);

    REP(i, N) {
        c[i] = a[i] * (m / s) + a[i] * (m % s) / s;
        rest -= c[i];
        nodes[i].r = (a[i] * (m % s)) % s;
        nodes[i].i = i;
        if(b[i] != 0 && c[i] < b[i] - 1) {
            ok = false;
            break;
        }
    }
    if(!ok) return false;

    stable_sort(nodes.begin(), nodes.end(), std::greater<Node>());
    vector<Node>::iterator it = nodes.begin();
    while(rest > 0) {
        c[(*it).i] += 1;
        rest--;
        ++it;
    }

    REP(i, N) {
        if(c[i] < b[i]) {
            return false;
        }
    }

    return true;
}


int main() {
    cin >> N;

    a = vector<ULL>(N);
    b = vector<ULL>(N);
    c = vector<ULL>(N);

    s = 0;
    ULL sb = 0;
    REP(i, N) {
        cin >> a[i] >> b[i];
        s += a[i];
    }

    ULL u = 50000000000000000ULL;
    ULL l = 0ULL;

    while(u > l+1) {
        ULL m = (u + l) / 2;
        if(check(m)) {
            u = m;
        } else {
            l = m;
        }
    }

    l = (u > 300 * N) ? u - 300 * N : 0ULL;
    for(ULL i=u; i>l; i--) {
        if(check(i)) {
            u = i;
            l = (u > 300 * N) ? u - 300 * N : 0ULL;
        }
    }
    cout << u << endl;

    return 0;
}