Codeforces Round #296:B. Clique Problem

問題

https://codeforces.com/contest/528/problem/B

考え方

各点について辺でつながることができる点を考えると間に合わないので工夫が必要である。辺でつながることのできる条件の余事象を考えてみる。

|x_i-x_j| \ge w_i + w_j の余事象は絶対値を展開して

 x_i - w_i \lt x_j + w_j \tag{1}  x_j - w_j \lt x_i + w_i \tag{2}

となる。

ここで実は以下の命題が成立することが知られている。(koba-e964さんに教えていただきました。ありがとうございます)。証明自体は難しくないと思う。

a \lt b, c \lt d を仮定した時、二つの閉区間 [a, b][c, d] が交差しないことと b \lt c\ or\ d \lt a が成立することは同値

裏も成立して、適当に修正すると

(a, b)と(c, d)が交差する \Leftrightarrow\ c \lt b\ and\ a \lt d \tag{3}

ことが言える。よって (1),(2),(3) より、ある 2(i,j) が辺でつながらないとき必要十分条件

 (x_i - w_i, x_i + w_i)(x_j - w_j, x_j + w_j) が交差する

ということが分かる。ここまで来ると求める最大クリークサイズは、それぞれの区間で交差しないように区間を選ぶときの最大の数であることが分かるので区間スケジューリング問題に帰着することがわかる。

https://codeforces.com/contest/528/submission/48402318

どこに着目して考察するべきだったか

辺でつながらない点の集合=余事象に着目すると見通しがよくなる気がする。余事象の条件から区間の交差の条件にたどり着くのが難しい。 区間の交差の命題

  • 閉区間[a, b]と[c, d]が交差しない \Leftrightarrow\ b \lt c\ or\ d \lt a

はまたどこかでお目にかかるかもしれない。

何がバグっていたか

得た知見(典型ポイント)

  • 余事象で考える
  • 同値で言い換える

類題