ARC106-Cの解答

AtCoder Regular Contest106-C Solution の解答を書いていきます。

問題はこちらから。

C - Solutions

Difficulty 1198 （緑）

問題

２つの区間[L1:R1], [L2:R2]について、L1<=R2かつ、L2<=R1のとき、この区間が交わるとします。&nbsp;

次の問題を考えます。

入力：n 個の区間&nbsp;[L1:R1], ... ,[Ln:Rn]
このとき、L1, ... ,Ln, R1, ... ,Rnはすべて異なる。
出力：どの2つの区間も交わらないように選べる区間の最大数。

このとき、２人が異なる方法で区間の数え上げをしました。

１人目：Riの値が昇順となるように区間を並べる。
２人目：Liの値が昇順となるように区間を並べる。
（並び替え後の区間を[Lp1:Rp1], ... ,[Lpn:Rpn]とする。）

i = 1, 2, ..., nについて、これまで選んだ区間と交わらないならば
[Lpi : Rpi]を選ぶ。

整数 n, mが与えられます。n 個の区間からなる問題の入力であって、

１人目の出力　－　２人目の出力　= m

となるケースを構築してください。構築できない場合は -1 を出力してください。

考察

n と mの値について場合分けして考えていきます。

( i ) m < 0のとき

１人目より、2人目の出力が大きい場合がこの場合に該当します。ところが、本問題は区間スケジューリングと呼ばれる問題であり、１人目の区間の終点を昇順に並べる手法が最適解となります。そのため、１人目の出力が２人目より小さくなることはありません。色々な状況を図に書いてみても、２人目の方が出力が大きい図は作れません。

本場合の際には、-1 を出力しましょう。

( ii ) m = n のとき

n >= 1 ですので、２人目の出力が 0 となることはありません。どんな状況でも、少なくとも1つは区間を選択できます。

そのため、本場合においても -1 を出力します。

( iii ) m = 0 のとき

一人目と二人目の出力が等しい場合です。与えられた n 個分の区間を交わりがないように設置しましょう。

( iv ) m > 0 のとき（n >= m-2）

１人目が２人目より大きくなる場合です。どのような時にこうなるのかを考えます。

数直線上を見ていきます。２人目は区間の始点に到達したらその区間を選択します。このとき、その区間の終点に達するまでは他の区間を選択できません。一方、１人目は区間の終点に到達したら、その区間を選択します。

そのため、２人目が区間を選択できない場所にて、他の区間が存在した場合に、m の数が増加していきます。

上図のように大きい区間の内側に小さい区間を詰め込みましょう。k 個詰め込んだ際には、m = k-1 となります。k が m に満たない場合は赤の外側に交差しないように区間を敷き詰めましょう。
追記
k が mに満たない→k+1が n に満たない

さて、上記のように書きましたが、内側に k 個詰め込んでようやく、

m = k-1

が実現されます。また、この時に使用する、区間数は k+1 となります。
要は、m を実現するためにはそれよりも2つ余分に区間が必要ということです（大きい区間で１個、２が少なくとも1個作るので、m+1個作るための１個）。したがって、本条件では

n >= m+2

を満たさなければなりません。

補足です。if 文を書く順番に左右されますが、n = 1, m = 0 のコーナーケースに躓く恐れがあります。具体的には、( iv )の n >= m+2 を先に、( iii )のm = 0を後に書いた場合です。 ( iv )の条件では「構築できない」という出力となりますが、m = 0の条件の( iii )にて構築が可能です。実装の際には気を付けましょう。

実装

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using ll = long long;
using namespace std;


int main() 
{ 
   int n, m;
   cin >> n >> m;

   if (m < 0 || ((m > n-2)&& n > 1)) //コーナーケースに対応
   {
       cout << -1 << endl;

   }
   else if (m == 0) 
   {
       rep(i, n) cout << i * 2 + 1 << " " << i * 2 + 2 << endl;
   }
   else 
   {
       int r = 2 * (m + 1) + 2;//終点
       cout << 1 << " " << r << endl;
       rep(i, m+1) cout << i * 2 + 2 << " " << i * 2 + 3 << endl;

       n -= (m+2);
       while (n > 0)
       {
           cout << r + 1 << " " << r + 2 << endl;
           r += 2;
           --n;
       }

   } 
  
   return 0;
}

おわりに

テストケースを構築するという一風変わった問題でした。やるべきことはそこまで難しくないのですが、条件を適切に場合分けをして、例外？といいますか、少し特殊なケースを漏らさず網羅するのは、なかなか大変ですね。

解説を読めば「なんだそんなことか」となるけど、コンテスト中にacできるかといわれると自信がなくなる問題だったのではないでしょうか？こういう問題にて、情報を処理していくのは骨が折れますね。