AtCoder Regular Contest 106, C : Solutions

問題文

　https://atcoder.jp/contests/arc106/tasks/arc106_c

問題概要*1

　区間スケジューリング問題を解く 2 つのアルゴリズムを考える．

• アルゴリズム 1 （高橋くん） : 区間を右端点の座標値でソートした後，先頭から舐め，選べるものをすべて選んでいく貪欲法
• アルゴリズム 2 （青木くん） : 区間を左端点の座標値でソートした後，先頭から舐め，選べるものをすべて選んでいく貪欲法

　整数 $N, M $ が与えられる．$N$ 個の区間からなる区間スケジューリング問題であって，「高橋くんが選べる区間の数」$-$「青木くんが選べる区間の数」が $M $ となるインスタンスを構成せよ．存在しない場合は代わりに $-1$ を出力せよ．

制約

• $1 \leq N \leq 2 \times 10^5$
• $-N \leq M \leq N$

解法

　いくつかのケースについて観察してみます．まず，高橋くんのアルゴリズムは最適なアルゴリズム[1]なので，$M < 0$ となるケースは作れません．次に，互いに交わらない区間を適当に並べると，どちらのアルゴリズムもすべての区間を選べるので，$M = 0$ なケースは簡単に作れることが分かります．また，どちらのアルゴリズムも最低一つの区間を選べるので，$M = N$ なケースは作れません．
　で，やや天啓的なのですが，

-------
 -- --

とすると，$M = 1$ の場合を作れます（余っている区間は交わらないようにして適当に並べて消費）．同様に，

----------
 -- -- --

とすると $M = 2$ の場合を作れます．以下同様なので，区間の数が足りている範囲では割と自由な $M $ についてインスタンスを作れます．この手法では，$k$ 個の区間を使って $M = k - 2$ を達成しています．
　今までのをまとめると，実は $M = N - 1$ なケースが未解決です．ケースを作れると仮定して，何が起こるか考えてみます．まず，青木くんは一つ以上の区間を選ぶので，$M = N - 1$ を達成するには高橋くんはすべての区間を選ばなければなりません．一方で，すべての区間を選べるということは，すべての区間に交わりはないので，青木くんのアルゴリズムでも選べるはずということになってしまいます．結局，仮定が誤りということで，やや雑ですが，背理法的にこのケースは作れないということが分かります．
　全体をまとめれば，

• $M < 0, M = N$ は無理
• $M = 0$ は互いに交わらない区間を適当に並べるとできる
• $M = 1, 2, 3, \dots, N - 2$ は違いに交わらない区間たちに長い区間をかぶせると作れる
• $M = N - 1$ は無理

ということになります．
　あとは適当に構成パートのプログラムを書けばよくて，計算量としては $O( N + M )$ 時間とかのを実装できます．

参考文献

[1] 秋葉拓哉, 岩田陽一, and 北川宜稔. "プログラミングコンテストチャレンジブック." (2010).

コード

int main()
{
	IN( int, N, M );

	if ( N == 1 && M == 0 )
	{
		cout << "1 2" << endl;
		return 0;
	}

	if ( M < 0 || N - 1 <= M )
	{
		cout << -1 << endl;
		return 0;
	}

	VPII res;
	res.EB( 1, 1 );
	--N;
	++M;
	for ( ; M; --M, --N )
	{
		const int l = res.back().snd + 1;
		res.EB( l, l + 1 );
	}
	res[0].snd = res.back().snd + 1;

	while ( N-- )
	{
		const int l = res.back().snd + 2;
		res.EB( l, l + 1 );
	}

	FOR( p, res )
	{
		cout << p.fst << ' ' << p.snd << '\n';
	}
	cout << flush;

	return 0;
}

*1:丁寧な説明は原文参照