AtCoder ARC #106 : C - Solutions

遅れて参加したけど、時間通り出ても全完はできてなさそう。
https://atcoder.jp/contests/arc106/tasks/arc106_c

問題

1次元座標上にN個の区間があったとする。

• アルゴリズムAでは、各区間を終端の昇順に並べ、貪欲に既存の選択済みの区間と重複しない場合区間を選択していく。
• アルゴリズムBでは、各区間を始点の昇順に並べ、貪欲に既存の選択済みの区間と重複しない場合区間を選択していく。

前者と後者で、選択した区間の差がMとなるよう区間を配置せよ。

解法

前者は最適な選択が可能なので、Mが負にはなりえない。
また、全区間最初から重複しないようにすればM=0を達成できる。
あとはMが正のケースを考えよう。

始点がとても手前にあって、終端がとても後ろにある区間を準備すると、アルゴリズムBではその1個しか選択できないが、アルゴリズムAではその区間に内包される他の区間を選択できる。
そこで、大きな区間を1個作った後、その内部に互いに重複しない区間を(M+1)個作ろう。余った(N-(M+2))個の区間は後ろに適当に置く。

int N,M;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	vector<pair<int,int>> ret;
	
	if(M>0) {
		if(M>N-2) {
			cout<<-1<<endl;
			return;
		}
		ret.push_back({1,500000});
		FOR(i,M+1) {
			ret.push_back({10+i*2,10+i*2+1});
		}
		FOR(i,N-(M+2)) ret.push_back({500010+i*2,500010+i*2+1});
	}
	else if(M==0) {
		FOR(i,N) ret.push_back({10+i*2,10+i*2+1});
	}
	else {
		cout<<-1<<endl;
		return;
	}
	
	FORR(r,ret) {
		cout<<r.first<<" "<<r.second<<endl;
	}
}

まとめ

M=0で割とはまった人がいたらしい？