最後の2問が自力で解けず。最後の問題はまだ解けていない。
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_j
問題
2つの学校にそれぞれN,M人の生徒がおり、各人のレートが与えられる。
両チーム生徒をA,Bの2チームに分ける。
その際、チーム内の総レートはAチームの方が高くなくてはならない。
そうして2つの学校で対戦する。
対戦は両校のAチーム同士およびBチーム同士が対戦し、レートが高い方が勝ちである。
2つ目の学校は、条件を満たすチームの組み合わせを等確率で選択する。
1つ目の学校のチーム分けを条件の範囲で任意に選べるとき、両チームで勝ちとなる確率の最大値を求めよ。
解法
N,Mはさほど大きくないので、まず両校全通りA,Bチームのレートの組み合わせを列挙しよう。
次にBチームのレートを座標圧縮しておく。
あとは、両校Aチーム昇順でソートしておき、尺取り法の要領で処理する。
1つ目の学校を、Aチームのレートの低い順に処理していこう。
その際、尺取り法の要領で、2つ目の学校のAチームのうち、それよりレートが低いものに対し、BITで対応するBチームのレートを数え上げる。
そうするとこのBITを参照することで、1つ目の学校がBチームのレートでも勝てるケースを数え上げられる。
int N,M; ll A[20],B[20]; vector<pair<ll,ll>> As,Bs; vector<ll> C; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} }; BIT<ll,20> bt; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) cin>>A[i]; FOR(i,M) cin>>B[i]; int mask; for(mask=1;mask<(1<<N)-1;mask++) { ll a=0,b=0; FOR(i,N) { if(mask&(1<<i)) a+=A[i]; else b+=A[i]; } if(a>b) As.push_back({a,b}); } C.push_back(0); for(mask=1;mask<(1<<M)-1;mask++) { ll a=0,b=0; FOR(i,M) { if(mask&(1<<i)) a+=B[i]; else b+=B[i]; } if(a>b) { Bs.push_back({a,b}); C.push_back(b); } } sort(ALL(As)); sort(ALL(Bs)); sort(ALL(C)); C.erase(unique(ALL(C)),C.end()); double ret=0; x=0; FORR(a,As) { while(x<Bs.size() && Bs[x].first<a.first) { y=lower_bound(ALL(C),Bs[x].second)-C.begin(); bt.add(y,1); x++; } y=lower_bound(ALL(C),a.second)-C.begin(); ret=max(ret,(double)bt(y-1)); } ret/=Bs.size(); _P("%.12lf\n",ret); }
まとめ
尺取り法とBITの応用。
500ptか600ptか迷う難易度だけど、最近のABCの600ptよりは簡単かも。