yukicoder : No.448 ゆきこーだーの雨と雪 (3)

4・5問目は近いタイミングで解いた人が多かったので、参加が数分遅れたのがかなり響いた。
http://yukicoder.me/problems/no/448

問題

N個の問題がある。
各問題iは時刻T[i]に実施され、難易度はD[i]である。

このうちいくつかの問題を取り除くことができる。
ただし取り除く問題同士はK以上時間が空いていなければならない。

残された問題の難易度の最大値を最小化し、その値を求めよ。
またその時、残された問題の難易度の総和を最小化し、その値を求めよ。

解法

難易度の最大値の最小化は二分探索で求めよう。
この値をAとする。
A以上の難易度の問題は必ず取り除くのでD[i]=0とみなす。
それ以外の難易度の総和を求めたのち、さらに取り除けるものがあれば取り除き、取り除く難易度の総和を最大化しよう。
A以上の難易度の問題に対し、前後K未満の時刻に開催される問題は取り除けないのでやはりD[i]=0とみなす。

以下の状態を考える。
dp[i] := 先頭からi番目の問題のうち取り除ける難易度の総和の最大値
i問目の前に取り除いたのがK以上前の時刻なら、i問目の問題を取り除いてもよい。
よってdp[i] = max(dp[i-1], dp[x] + D[i])とする。(ただしxはT[x]≦T[i]-Kであるようなx)

尺取り法の要領でdp[x]の最大値を管理していけばこのDPは全体でO(N)で行える。

int N,K;
ll T[202020],D[202020];
int NG[202020];
ll dp[202020];


int ok(int can) {
	int pre=-1<<30;
	int i;
	FOR(i,N) if(D[i]>can) {
		if(T[i]-pre<K) return 0;
		pre = T[i];
	}
	return 1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>T[i]>>D[i];
	
	int ma=(1<<30)-1;
	for(int i=29;i>=0;i--) if(ok(ma-(1<<i))) ma-=1<<i;
	cout<<ma<<endl;
	
	ll pre=-1LL<<40;
	FOR(i,N) {
		if(D[i]>ma) pre = T[i];
		else if(T[i]-pre<K) NG[i]=1;
	}
	pre=1LL<<40;
	for(i=N-1;i>=0;i--) {
		if(D[i]>ma) pre = T[i];
		else if(pre-T[i]<K) NG[i]=1;
	}
	
	ll sum=0;
	FOR(i,N) {
		if(D[i]>ma) {
			D[i]=0;
		}
		else {
			sum+=D[i];
			if(NG[i]) D[i]=0;
		}
	}
	
	ll tma=0;
	x=0;
	FOR(i,N) {
		while(T[i]-T[x]>=K) tma=max(tma,dp[++x]);
		dp[i+1]=max(dp[i], tma+D[i]);
	}
	
	cout<<sum-dp[N]<<endl;
}

まとめ

もう少し短く書きたいけどどう書くとシンプルに書けるんだろうな。