cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
SRM | |
SRM430 の成績・ソース (要ログイン) : AC/AC/TLE : ダメとほぼ確信しててsubmitするのはやめた方がいいのかな
rec( i:次繋げる都市番号, v:残りくっつける都市数リスト ) {
[i+1 .. N) から v[i] 個以下(距離D制約を見たしつつ)都市をえらぶ選び方全部試してみる
}
あとで | |
他の方の参戦記を参考に解いた。そうか、半分にわければ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; } };
presented by
cafelier/k.inaba
under
