ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Codeforces Round #595 (Div. 3) D2. Too Many Segments (hard version)

お題箱より。

Problem - D2 - Codeforces

問題概要

整数を端点とする  n 個の閉区間  \lbrack l_{i}, r_{i}\rbrack が与えられる。これらから0個以上の区間を捨てて、全ての整数点について「その整数点を含んでいる区間 k 個以下である」という状態にしたい。

捨てる区間の最小個数と、その選び方の1例を求めよ。

制約

  •  1 \le k \le n \le 2\times 10^{5}
  •  1 \le l_{i} \le r_{i} \le 2\times 10^{5}

解法

小さい方を左として、左から順番に整数点を見ていきます。このとき各整数点について「今見ている整数点を含んでいる区間 k 個以下となる」ように区間を捨てていきます。

具体的には「残す区間であって、今見ている整数点を含むもの」の集合を管理するようにします。そして整数点  i を見る時には以下の処理をします。

  1.  i を左端とする区間を、いったん全て集合に入れる。
  2. 集合に含まれる区間数が  k 個を超えている場合、 k 個以下になるまで↓を繰り返す。
    • 集合の中で右端が最も右にある区間を捨て、集合から取り除く。
  3. 集合の中に  i を右端とする区間がある場合、この区間から出るので集合から取り除く。

この方法で捨てる区間の個数が最小となり、その選び方の1例を求められます。

その理由を考えてみましょう。この処理を左側の整数点から順に行っていくと、整数点  i を見るときにはそれより左の整数点は既に条件を満たしています。つまり集合に入っている区間 i より左側のどこまで伸びているかは、もはや考えなくて良いです。2.において捨てる区間を選ぶときには、 i より右側で最も邪魔になりやすい区間、つまり右端が最も右にある区間を捨てるのが常に最適になります。

つまり区間を管理する集合においても、左端は必要なくて右端の値(と出力のためのインデックス)が保持されていれば良いです。この集合に必要な機能は

  1. 含まれている区間の個数が分かる。
  2. 右端の値が最も大きい区間の番号を求め、取り除くことができる。
  3. 右端の値がある値と等しい区間を取り除くことができる。

ことです。これはC++であれば set 等で実現できます。

言語機能にない場合は、BIT等に入れておいて二分探索する等の方法があります。もしくはPython等にもある優先度付きキューで1.と2.の機能は実現できるので、3.を工夫して代用しても良いです。集合に入っている値の頻度表を別途作っておき、「区間から出る」ことで除かれるはずの要素数を別途計算しておけば、その分だけキューの中の要素数から差し引くことで同じことができます。

ACコード

リクエストくれた人の使用言語が分からなかったのですが、順序付き集合が使えるかどうかで若干実装が異なるのでC++Pythonの実装例を紹介しておきます。

私はこのコンテストの本番では区間加算ができるセグメント木を使いました。解法、実装手段は色々あると思います。