aoj0613:Treasures

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0613

解法

制約的に自明といえば自明ですが、半分全列挙しました。

まず、半分ずつ列挙します。具体的には、市場価値の差と貴重度の差をいっぱい求めます。

そして、後半を市場価値の差の値で昇順にソートします。

for文で前半を舐めます。このとき、前半の市場価値の差と後半の市場価値の差の合計が-D~Dの範囲に入らなければなりません。後半をソートしているため、そのような許容範囲の左端と右端は二分探索で求まります。

後半の許容範囲の中ならどれを選んでもよいです。よって、一番貴重度の差が大きいものをとります。ここで、普通にfor文で舐めたりしてしまうと計算量がやばいことになります。区間内の最大値ということで、RMQを用いれば対数時間で計算できます。

一応これでACすると思ったのですが、TLEしました。そこで、許容範囲の左端と右端を求めるときに二分探索しているところを改善しました。前半を市場価値の差で降順にソートしたうえでfor文で舐めると、後半の許容範囲の左端と右端が単調増加します。よって尺取法(?)っぽいなにかで左端と右端をインクリメントしていきます。すると、二分探索しなくてよくなるので、定数倍が少し改善されます。僕はこれでACしました。

実行時間制限がきつかったですが、JOI予選の問題なので本番ではTLEの恐れはありません。よって、そこまで気にしなくてもいいかもしれません。

始めのほうでセグメントツリーの要素数(SIZE)を2の冪乗にせずに実装したら、バグだらけになった。
小一時間デバッグに溶けた。気を付けようと思った。

下のコードではcin>>Y[i]>>X[i]のように市場価値と貴重度が逆に入力されていますが、これは途中まで市場価値と貴重度を逆に認識していたためです。(慌てて入力を逆に受け取ってみたらなんかうまくいった)

コード

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>P;//Pre val
#define fi first
#define se second

const int SIZE=16777216;
int dat[SIZE*2-1];
const int INF=LLONG_MAX/100;
void update(int k,int x){
    k+=SIZE-1;
    dat[k]=x;
    while(k){
        k=(k-1)/2;
        dat[k]=max(dat[k*2+1],dat[k*2+2]);
    }
}

int getMax(int a,int b,int k=0,int l=0,int r=SIZE){
    if(a<=l&&b>=r)return dat[k];
    if(r<=a||b<=l)return -INF;

    int m=(l+r)/2;
    int vl=getMax(a,b,k*2+1,l,m);
    int vr=getMax(a,b,k*2+2,m,r);
    return max(vl,vr);
}

int N,D;
int X[30],Y[30];

vector<P>A,B;
void Latte(int cur,int last,int val,int pre,bool after){
    if(cur==last){
        if(after)B.push_back(P(pre,val));
        else A.push_back(P(pre,val));
        return;
    }

    Latte(cur+1,last,val+X[cur],pre+Y[cur],after);
    Latte(cur+1,last,val-X[cur],pre-Y[cur],after);
    Latte(cur+1,last,val,pre,after);
}


signed main(){
    cin>>N>>D;
    for(int i=0;i<N;i++)cin>>Y[i]>>X[i];

    Latte(0,N/2,0,0,false);
    Latte(N/2,N,0,0,true);

    sort(A.rbegin(),A.rend());
    sort(B.begin(),B.end());
    fill_n(dat,SIZE*2-1,-INF);
    for(int i=0;i<B.size();i++){
        update(i,B[i].second);
    }

    int ans=-INF;
    int lb=0,ub=0;
    for(int i=0;i<A.size();i++){
        while(lb<B.size()&&-D-A[i].fi>B[lb].fi)lb++;
        while(ub<B.size()&&D-A[i].fi>=B[ub].fi)ub++;
        ans=max(ans,A[i].se+getMax(lb,ub));
    }
    cout<<ans<<endl;
    return 0;
}