JOI2011本戦 第五問「微生物実験」

JOI本戦のラスボス。
セグメント木を出してくるとは、さすがJOI。
（qnighyさんはpriority queue＋しゃくとり法みたいな感じで解いたそうな）

まずはセグメント木で実装し、次にBITでやってみます。

う〜ん、今回はソースコード見て理解して欲しいかも。
考え方というよりは、実装が難しい問題だと思うんで。
まずはセグメント木。

#include<cstdio>
#include<algorithm>
#include<vector>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;
typedef long long ll;

struct bug {int a, b, c;};
struct seg {int a, k;};

bool comp_a(const bug& x, const bug& y){ return x.a < y.a; }
bool comp_b(const bug& x, const bug& y){ return x.b > y.b; }

seg t[1<<20];
int n, n2, n3;
ll suma, sumk, lim;

bool max_k(int j){
	if (j > n3) return false;
	if (suma + t[j].a <= (sumk + t[j].k) * lim){
		suma += t[j].a;
		sumk += t[j].k;
		return true;
	}
	
	if (max_k(j*2)) max_k(j*2+1);
	
	return false;
}


int main(){
	int a, b, ans = 0;
	vector<bug> m;
	
	scanf("%d", &n);
	
	n2 = 1;
	while (n2 < n) n2 <<= 1;
	
	rep(i,n){
		scanf("%d%d", &a, &b);
		m.pb((bug){a, b, 0});
	}
	
	sort(m.begin(), m.end(), comp_a);
	rep(i,n) m[i].c = n2 + i;
	
	sort(m.begin(), m.end(), comp_b);
	
	n3 = 2*n2 - 1;
	rep(i,n){
		int j = m[i].c;
		t[j].a = m[i].a; t[j].k = 1;
		while (j > 0) {
			j /= 2;
			t[j].a += m[i].a;
			t[j].k ++;
		}
		
		suma = 0; sumk = 0; lim = m[i].b;
		max_k(1);
		ans = max(ans, int(sumk));
	}
	
	printf("%d\n", ans);
	
	return 0;
}

ちなみにgccなら、

while (n2 < n) n2 <<= 1;

は

n2 = 1 << (32 - __builtin_clz(n));

みたいにかけるそうです。
じゃあ次、BIT。

#include<cstdio>
#include<algorithm>
#include<vector>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;
typedef long long ll;

struct bug {int a, b, c;};
struct BIT {int a, k;};

bool comp_a(const bug& x, const bug& y){ return x.a < y.a; }
bool comp_b(const bug& x, const bug& y){ return x.b > y.b; }

BIT t[1<<19+1];

int main(){
	int n, n2, a, b, j, ans = 0;
	ll suma, sumk, lim;
	vector<bug> m;
	
	scanf("%d", &n);
	
	n2 = 1;
	while (n2 < n) n2 <<= 1;
	
	rep(i,n){
		scanf("%d%d", &a, &b);
		m.pb((bug){a, b, 0});
	}
	
	sort(m.begin(), m.end(), comp_a);
	rep(i,n) m[i].c = i + 1;
	
	sort(m.begin(), m.end(), comp_b);
	
	rep(i,n){
		j = m[i].c;
		while (j <= n2) {
			t[j].a += m[i].a;
			t[j].k ++;
			j += j & -j;
		}
		
		j = n2;
		suma = 0; sumk = 0; lim = m[i].b;
		while (j >= 1 && j <= n2) {
			int j2 = (j & -j) >> 1;
			if (suma + t[j].a <= (sumk + t[j].k) * lim){
				suma += t[j].a;
				sumk += t[j].k;
				j += j2;
			} else {
				j -= j2;
			}
			
			if (!j2) break;
		}
		
		ans = max(ans, int(sumk));
	}
	
	printf("%d\n", ans);
	
	return 0;
}

セグメント木・BITを書いたのは初めてなので、おかしいところとかあったら教えて下さいm(_ _)m

データ構造が分からない人は、この本を読みましょう！

プログラミングコンテストチャレンジブック

反省点

落ち着きが足りなかった。
それに尽きる。
合宿では冷静になろう！