[Codeforces] Educational Codeforces Round 58 C. Division and Union

Division and Union

考察が必要な良い問題だと思います。典型問題のような気もしました。

考え方

題意

\( n \) 個の閉区間 \( [l_i,  r_i]\) を二つのグループに分けることができるかどうかを調べます。グループ分けができるということは、\( r_i < l_j\) を満たすような区間があるということです。

方針

まず初めに、\( l_i \) について昇順に並び替えます。\( l_i = l_j \) の区間については並び順は問題ないと思います。

グループ分けができる区間は、\( r_i \leq x < l_j \) \( (i < j)\) を満たす \( x \) が存在します。整列された区間に対して、この \( x \) を更新していき条件を満たすかどうかを調べます。どのような更新が必要かというと、初期値は \( x = r_0\) とします。更新する条件は、

\[ x = \max (x, r_i)\]

となります。

コード

感想

最初考えた方法はいもす法で塗りつぶされる区間をカウントしたりするのかと思ったんですが、ダメでした。アルゴリズム的には整列だけですが、解けませんでした。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする