SRM 430 Div1 Hard PickingUp

問題概要

キャプテン二人がN人を、人数の等しい二つのチームに分けたい。
各人にはそれぞれのキャプテンから見たscore1[i],score2[i]が定められている。

各チームの(自己)評価の差が最小になるようなチームの分け方を求めよ。
そのような分け方が複数あるときは辞書順で最小のものを求めよ。

制約条件

N≦36かつNは偶数。

方針

蟻本でも解説されている、半分ずつ全列挙して、二分探索の問題。


前半のN/2人のチーム分けtと、その時のスコアをsとしたとき、
後半では-sになるべく近いスコアで、なおかつtと合わせるとN人になるチーム分けを二分探索により求めてやる。

辞書順最小の条件がついているので、スコアと一緒にチーム分けの方法も持たなければならないので実装がちょっと大変。


以下のコードでは、left[i]に前半がi人チーム1に入っている場合の分け方を全列挙したvector,
right[i]を後半の(以下同様)、として、
left[i]のそれぞれに対してソートしておいたright[n/2-i]から、二分探索により、もっともスコアが足して0に近いようになるright[n/2-i]の要素を求めている。

基本的にlower_boundでよいのだけれど、同点の分け方があった場合、辞書順最小なので、そのスコアで辞書順最小のチームを求めるのに再度lower_boundを使う。

ソースコード

class PickingUp {
  public:
  vector <int> fairPickingUp(vector<long long> score1, vector<long long> score2) {
    int n=score1.size();
    
    vector<pair<ll,ll> >left[20], right[20];
    rep(i,1<<n/2){
      ll sum=0, t=0;
      int cnt=0;
      rep(j,n/2){
        if(i&1<<j)sum+=score1[j], cnt++;
        else sum-=score2[j], t|=1ll<<n-1-j;
      }
      left[cnt].pb(mp(sum,t));
    }
    rep(i,1<<n/2){
      ll sum=0, t=0;
      int cnt=0;
      rep(j,n/2){
        if(i&1<<j)sum+=score1[j+n/2], cnt++;
        else sum-=score2[j+n/2], t|=1ll<<n/2-1-j;
      }
      right[cnt].pb(mp(sum,t));
    }
    rep(i,n/2+1)sort(all(right[i]));

    pair<ll,ll> ans=mp(1ll<<60,0);
    rep(i,n/2+1)fr(j,left[i]){

      if(right[n/2-i].empty())continue;

      vector<pair<ll,ll> >::iterator a[2],prev;
      a[0]=lower_bound(all(right[n/2-i]),mp(-j->first,0ll));
      if(a[0]==right[n/2-i].end())a[1]=right[n/2-i].end(), a[1]--;
      else if(a[0]==right[n/2-i].begin())a[1]=right[n/2-i].end();
      else a[1]=a[0], a[1]--;

      rep(k,2)if(a[k]!=right[n/2-i].end()){
        if(a[k]!=right[n/2-i].begin()){
          prev=a[k]; prev--;
          if(prev->first==a[k]->first)a[k]=lower_bound(all(right[n/2-i]),mp(prev->first,0ll));
        }
        ll sum=abs(j->first + a[k]->first), t=j->second | a[k]->second;
        ans=min(ans,mp(sum,t));
      }
    }
    vi ret;
    rep(i,n)ret.pb((ans.second&1ll<<n-1-i)?2:1);
    return ret;
  }
};