Algoogle

Algorithm for Programming Contest

PA 2010 Sweets

Category: PA Tag: geometry, line-sweep, math

Sweets

問題概要


n(<=24)個の箱にそれぞれ個のお菓子がある.
これを3人兄弟Anton, Dmytro, Borysで箱ごとに配りたい.
できるだけ平等に分けるとき最小のAntonとBorysのもらう数の差を求めよ.
ただしそれぞれのもらう数A, D, Bはを満たさなければならない.

解法


まずn個の箱を半分ずつ()に分ける.
これは半分ずつ全列挙することで全体で全列挙するのを抑えるため.
それぞれの集合で3人がもらう数をとする.
のありうる組を全列挙しておく.
列挙した組の集合をそれぞれとする.

ここで以下のような変換をする.

これによって求める最小値はの要素について

の最小値となる.
ただしを満たす組のみ.
なぜなら

を満たさなければならないから.

この条件から2次元上の最近点(マンハッタン距離)を求めれば良い.
条件よりの点を固定してと考えると, 最も近いの条件を満たす点というのは
それより左下にあるもののうち, x+yが最大になる点とわかる.
これは2つの集合の点を混ぜてyの昇順に見ていけば
の点pのとき, それまでに出てきたの点のうちx座標についてp以下にあって, x+yが最大に点が一番近い.
の点pのとき, 登場済みリストに入れる. ただしx座標についてそれ以降の点でx+yの値ががp以下のものは選ばれることが無い(もしくはそれを選ぶ必要がない)ので予め削除する.

2つ目の操作から登場済みリストはxについて単調増加であり, またx+yについて単調非減少になる.
これの性質を利用することで1つ目の操作はx座標についてp以下のもののうち一番近いものを2分探索で選べばよく, 2つ目の操作はx座標についてp以上かつx+yについてp以下の点の区間を2分探索で求め削除することができる.

計算量は列挙に, 各操作にとなる.
よって全体ではとなりなんとか間に合う.

コード


(sweets.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

struct point
{
        long long x, y;
        int k;
        point(long long x, long long y, int k) : x(x), y(y), k(k) {}
        bool operator<(const point &p) const { return x!=p.x? x<p.x: y<p.y;}
};
inline bool cmpy(const point &a, const point &b) { return a.y!=b.y? a.y<b.y: a.x!=b.x? a.x<b.x: a.k>b.k;}

const long long inf = 1LL<<50;
int n[2];
long long a[2][32], sum[2][32];

long long solve()
{
        vector<point> vs;
        for (int k = 0; k < 2; k++) {
        for (int s = 0; s < 1<<n[k]; s++) {
                int m = n[k]-__builtin_popcount(s);
                for (int t = 0; t < 1<<m; t++) {
                        long long x = 0, y = 0, z = 0, j = 0;
                        for (int i = 0; i < n[k]; i++) {
                                if(s>>i&1) x += a[k][i];
                                else {
                                        if(t>>j&1) y += a[k][i];
                                        else z += a[k][i];
                                        j++;
                                }
                        }
                        vs.push_back(point((1-k*2)*(x-y),(1-k*2)*(y-z),k));
                }
        }
        }
        sort(vs.begin(),vs.end(),cmpy);
        long long ans = inf;
        vector<point> S; // (x, x+y)
        for (vector<point>::iterator p = vs.begin(); p != vs.end(); p++) {
                if(p->k == 0) {
                        vector<point>::iterator q = upper_bound(S.begin(), S.end(), point(p->x,inf,0));
                        if(q == S.begin()) continue;
                        q--;
                        ans = min(ans, p->x+p->y-q->y);
                }
                else {
                        vector<point>::iterator l = lower_bound(S.begin(), S.end(), point(p->x,-inf,0)),
                                                r = upper_bound(l, S.end(), point(inf,p->x+p->y,0), cmpy);
                        S.erase(l, r);
                        S.insert(l, point(p->x, p->x+p->y, 0));
                }
        }
        return ans;
}

void input()
{
        scanf("%d", n);
        n[1] = n[0]/2;
        n[0] -= n[1];
        for (int i = 0; i < n[0]; i++) scanf("%lld", a[0]+i);
        for (int i = 0; i < n[1]; i++) scanf("%lld", a[1]+i);
}

int main()
{
        input();
        printf("%lld\n", solve());
        return 0;
}

Comments