UTPC 2013 : G - 夏休みの掃除当番

UTPC2013の200pt問題を練習。ここらへんは自力で解にたどり着けてないので解説を見ながらトライ。
http://utpc2013.contest.atcoder.jp/tasks/utpc2013_07

問題

M日間の夏休みの間に、N人の学生が来る。
各学生はA[i]日目～B[i]日目のうち１回だけ来てもらい、部屋の掃除を依頼できる。
ただし、N人中K人にはA[i]～B[i]日目の間毎日来てもらい毎日掃除してもらうことができる。

部屋の掃除間隔の最小日数を求めよ。

解法

最小日数を求める問題なので、日数を二分探索で求めて行けばよい。

現在の日付をC、仮置きした日数をDとする。
C=0からC=M+1に至るまでの期間に学生の来る日を配置していく。

基本的には各学生は１回しか来ないので、C～(C+D)日の範囲内までに来る学生のうち、B[i]が小さい順に選択し、C=min(C+D,B[i])で更新していけばよい。
ただし、C～(C+D)日の間に来られる学生がいなくなる場合がある。
この時はK人まで選択できる毎日来る学生を１人消費し、B[i]が最大の学生を選びC=B[i]で更新すればよい。

２分探索回数がO(logM)、１回の探索がO(N*logN)なので全体でO(N*logN*logM)で処理可能。

int N,M,K;
pair<int,int> P[100010];

int okok(int dist) {
	int kk=K;
	int day=0,s=0,ma=0;
	
	priority_queue<int,vector<int>,greater<int> > Q;
	
	while(day+dist<M+1) {
		while(s<N && day+dist>=P[s].first) {
			Q.push(P[s].second);
			ma=max(ma,P[s].second);
			s++;
		}
		
		if(Q.empty()) {
			if(kk<=0 || day>=ma) return 0;
			kk--;
			day = ma;
		}
		else {
			if(Q.top()>day) day = min(day+dist, Q.top());
			Q.pop();
		}
	}
	return 1;
}


void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>K;
	FOR(i,N) cin>>P[i].first>>P[i].second;
	sort(P,P+N);
	int L=1,R=M;
	while(L<R) {
		int po=(L+R)/2;
		if(okok(po)) R=po;
		else L=po+1;
	}
	while(okok(R-1)) R--;
	while(!okok(R)) R++;
	
	_P("%d\n",R);
}

まとめ

む、これは本番に思いつけても良かったかもしれない。