TopCoder SRM 645 Div1 Easy JanuszTheBusinessman

SRM645、Mediumは方針が合ってたのにもうちょっとってところで落としてしまった。
Easyも微妙に遅いうえ、2Challenge missが痛かった。
とはいえ意外に正答者が少なくレート維持。
http://community.topcoder.com/stat?c=problem_statement&pm=13603

問題

あるホテルの宿泊者N人に関し、チェックイン・チェックアウトの日付が与えられる。
ホテルのオーナーはN人全員のレビューを入手したかった。

オーナーが直接特別サービスをした宿泊者は、レビューを作成してくれる。
また、特別サービスをした宿泊者と滞在日が重複した宿泊者もレビューを作成してくれる。

全員のレビューを得るために、特別サービスを行う必要のある宿泊者の最小数を求めよ。

解法

まず宿泊者をチェックアウト日でソートする。

レビュー未作成の宿泊者のうち、最もチェックアウト日が早いの宿泊者に対し、滞在期間にそのチェックアウト日を含む宿泊者のうち最もチェックアウト日が遅い宿泊者に特別サービスを行うと、最もチェックアウト日が早いの宿泊者をカバーしつつ、最も長い期間に対応した宿泊者のレビューを得られる。

あとはレビュー未作成の宿泊者がいなくなるまで上記処理を繰り返すだけ。

class JanuszTheBusinessman {
	public:
	
	int makeGuestsReturn(vector <int> A, vector <int> D) {
		int N=A.size();
		pair<int,int> P[51];
		
		int i,x,y;
		FOR(i,N) P[i]=make_pair(D[i],A[i]);
		sort(P,P+N);
		
		int ret=0;
		int vis[51]={};
		FOR(i,N) if(vis[i]==0) {
			int td=P[i].first;
			int mi=-1;
			ret++;
			FOR(x,N) if(P[x].second<=td && td<=P[x].first) {
				if(mi==-1 || P[mi].first<P[x].first) mi=x;
			}
			FOR(x,N) {
				if(min(P[mi].first,P[x].first)-max(P[mi].second,P[x].second)>=0) vis[x]=1;
			}
		}
		
		return ret;
	}
}

まとめ

CodeforcesでN≦10^5位で出そう。