競プロで出てもおかしくない!数オリの構築系問題 その3

そのいくつまで続くかはわかりませんが、いい感じの問題を見つけたら暇を見つけて書いていこうと思います!

趣旨

  • 各国の数オリで出た問題で競技プログラミングの問題にもなりそうな問題を集めて紹介
  • 原案はそのまま、場合によっては原文が証明問題のものも使用していい感じの問題文に改変して紹介 といった感じで行こうと思います。

例としては、「○○に対して□□を満たす△△が必ず存在することを示せ」という問題があったとしたら、「○○が与えられるので、□□を満たすような△△を出力せよ」に変える、って感じです。

今回の問題はだま氏(@dama_math)から教えてもらいました。 国際数学オリンピック(IMO)からです。
IMOと聞くと難しそうに聞こえるかもしれませんが、1986年の3番級なので、今に比べるとかなり簡単だと思います。

問題概要

平面上に N 個の点がある。i 個目の点の座標は (x _ i,y _ i) である。
この時、以下の条件を満たすように点を白または黒で塗り分けることは可能か。

  • 座標軸のどちらかに平行な任意の直線上の白色の点と黒色の点の数の数の差が一個以下

可能な場合は構成し、不可能な場合は-1を出力せよ。

制約

  • \(N \le 10 ^ 5\) , 整数
  • \(x _ i , y _ i \le 10 ^ 9\) , 整数

現問題url (IMO 1986 問題6)

AGC換算で 800~900 くらいだと思います(個人の感想)

ヒント1 結論から言うとどんな場合でも可能です

ヒント2 グラフです。

ヒント3 頂点が直線、与えられた点が辺のグラフを考えてみてください。

解答 結論を言うと、常に可能です。以下それを示し、構成します。
与えられた点集合のうち一つでも通るような座標軸に平行な直線を頂点とするグラフを考えます。
 (x _ i , y _ i) に対し、  x = x _ i ~~ y = y _ i の二直線の(グラフにおける)頂点を結ぶ辺をグラフに追加します。 このようなグラフにおいて、問題文の条件を言い換えてみます。すると、次のようになります。

  • 無向グラフが与えられる。辺を向き付けることで任意の頂点において入次数と出次数の差が1以下になるようにできるか。

ところで、任意の無向グラフは端点が両方奇数次の頂点であるようなパス (その上、端点は重複しない) とループに分解できることが知られています。これは辺の数に対する帰納法で簡単に示せます。
これらのパスとループを全て同じ方向に向きつけると条件を満たすことは簡単にわかります。

実装としては、

  • 奇数次の頂点が残っている限り、その頂点から奇数次の頂点に到達するまで辺を取り除きながらdfsする。
  • 上の操作後は偶数次の頂点のみ残っているので、適当な頂点からdfsすることでループに分解できる。

のようにすればよいと思います。

所感 グリッドとかでも行、列を頂点、点を辺にすると見通しがよくなる問題めっちゃあるね、、、必ず一回は試すようにしたいです。