CSAcademy Round #41 : E. Candles

前半手間取ったけど何とか後半挽回。
https://csacademy.com/contest/round-41/task/candles/

問題

N個のろうそくがあり、個々の長さはH[i]である。
ろうそくは１日単位で火をつけたり消したりでき、１日火をつけると１長さが短くなる。

ここでM日の日程に対し、i日目でつけておきたいろうそくの数C[i]が与えられる。
最適な順でろうそくに火をともすとき、最長何日目まで条件を満たせるか。

解法

ろうそくをともす場合、長いものを優先的に利用するとよいのは明らかである。
よって、ろうそくの長さを昇順に並べ、i日目には上位C[i]個をデクリメントし、また長さを昇順に維持するようなデータ構造があればよい。
(途中上位C[i]番目をデクリメント後値が負になると、条件が満たせないことになる。

自分はBITを使い管理した。
まず初期状態でろうそくを昇順に並べ、i番目がH[i]となるよう差分を取ってBITに入れよう。

毎日、BITにおいて(N-C[i]+1)番目の値を参照しそれが正ならその日は条件を満たす。
次にデクリメントであるが、(N-C[i]+1)～N番目をすべてデクリメントするには、BITにおいて(N-C[i]+1)番目の差分に-1を加えればいいので高速に行える。
ただ、問題はもともと(N-C[i])番目と(N-C[i]+1)番目に差がない場合、デクリメントにより昇順が崩れることである。

そこで二分探索を用いて、(N-C[i]+1)番目と同じ値のうち最小のindex Aと、(N-C[i]+1)番目より大きなと同じ値のうち最小のindex Bを求めよう。
B以降は普通にデクリメントし、昇順を維持するには、A～(B-1)番目のうち手前からいくつかをデクリメントするようにすればよい。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	V set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};


int N,M;
int H[101010],C[101010];
BIT<int,20> bt;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	FOR(i,N) cin>>H[i];
	sort(H,H+N);
	bt.add(0,H[0]);
	for(i=1;i<N;i++) bt.add(i,H[i]-H[i-1]);
	bt.add(N,201010);
	
	FOR(i,M) {
		cin>>C[i];
		if(C[i]>N) break;
		y=N-C[i];
		x = bt.total(y);
		if(x<=0) break;
		
		x=bt.lower_bound(bt.total(y));
		k=bt.lower_bound(bt.total(y)+1);
		bt.add(k,-1);
		bt.add(x,-1);
		bt.add(x+(k-y),1);
	}
	
	cout<<i<<endl;
	
	
}

まとめ

このデータ構造は今後も使えそう。