cafelier@SRM

SRM430 Div1 1000 (2008/12/21)

あとで | 10:40 |

他の方の参戦記を参考に解いた。そうか、半分にわければ2^18は全通り試せるのか。なるほどなあ。尺取りメソッドというのは毎回二分探索するかわりに左と右から少しずつずらしていけばO(NlogN)がO(N)で済むという手のことかな。

あとこれ、人数合わせる制約なしの一般のPARTITIONにも O(N 2^(N/2)) くらいで使えるなー。勉強になった

class PickingUp
{
public:
  vector<int> fairPickingUp(vector<long long> score1, vector<long long> score2) 
  {
    LL t = accumulate(score2.begin(), score2.end(), 0LL);
    vector<LL> s;
    transform(score1.begin(), score1.end(), score2.begin(), back_inserter(s), plus<LL>());

    int N = s.size() / 2;

    vector< map<LL,BITS> > L = try_all( s.begin(), N );
    vector< map<LL,BITS> > R = try_all( s.begin()+N, N );

    pair<LL, BITS> best(0x7fffffffffffffffLL, 0);
    for(int i=0; i<=N; ++i)
      best = min(best, best_possible( L[i], R[N-i], t, N ));

    vector<int> ans;
    for(int i=0; i!=s.size(); ++i)
      ans.push_back( (-best.second & (1LL<<s.size()-1-i)) ? 1 : 2 );
    return ans;
  }

  pair<LL, BITS> best_possible( map<LL,BITS>& L, map<LL,BITS>& R, LL t, int N )
  {
    typedef map<LL,BITS>::iterator mit;

    pair<LL, BITS> best(0x7fffffffffffffffLL, 0);
    for(mit i=L.begin(); i!=L.end(); ++i)
    {
      LL as = i->first;
      LL am = i->second;
      mit j = R.lower_bound(t-as);
      if( j!=R.end() ) {
        LL bs = j->first;
        LL bm = j->second;
        best = min(best, make_pair(abs(as+bs-t), -((am<<N)|bm)));
      }
      if( j!=R.begin() ) {
        --j;
        LL bs = j->first;
        LL bm = j->second;
        best = min(best, make_pair(abs(as+bs-t), -((am<<N)|bm)));
      }
    }

    return best;
  }

  template<typename Ite>
  vector< map<LL,BITS> > try_all( Ite s, int N )
  {
    vector< map<LL,BITS> > a(N+1);
    for(BITS m=(1<<N)-1; m>=0; --m)
    {
      int nb = 0;
      LL  sm = 0;
      for(int i=0; i<N; ++i)
        if( m & (1LL<<N-1-i) )
          ++nb, sm+=*(s+i);
      if( !a[nb].count(sm) )
        a[nb][sm] = m;
    }
    return a;
  }
};