kmjp's blog

競技プログラミング参加記です

技術室奥プログラミングコンテスト#4 Day1 : J - school competition 2

最後の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よりは簡単かも。