天才数え上げな見た目をしているのにゴリゴリデータ構造ゲーに落ちるという面白い問題。
かなり苦戦して通したので整理しようと思う。
問題
小課題1
条件を満たすように、区間の集合を2つのグループに分けた時の通り数を求める問題。
問題文にやることが書いてあるので、O(2^N)で全探索した後にO(N)でシミュレーションすれば良い。これでO(2^N*N)で解けた。
小課題2
どういう時に条件を満たすか考えると、「同じグループ内に、部分的に交差している2つの区間が存在しない」時だと分かる。
このような区間同士に辺を張ったグラフを考える。グループ分けを頂点への色塗りとして捉えると、辺の2端点の色が全て異なることが条件。
つまり、求めるものは二部彩色の通り数である。
二部グラフでないならば答えは0。二部グラフならば、連結成分ごとに2通りの彩色方法があるので、2^(連結成分数)が答えとなる。
二部グラフ判定と連結成分数を求めるのはDFSで容易にでき、グラフの辺数はO(N^2)本なので、O(N^2)で解けた。
小課題3・4
定石通り、区間を左端でソートし、順に見ていく。
この時、iと辺が張られるのは、「今までに出てきた区間のうち、Ai≦右端≦Biのもの」である。
区間にまとめて辺を張りたいので、Segment Treeで右端を管理してみよう。
各ノードには、「ノードが表す区間に含まれる、今までに出てきた右端の集合」を乗せる。
まず、連結成分数だけを求めることを考える。
「[Ai,Bi]に対して辺を張る」というクエリが飛んできたら、それが被覆するノード内の集合とiが同じ連結成分になるので、これら全てと辺を張れば良い。
こうすることで、愚直に張ったグラフと連結性が等しいグラフが出来上がる。
これだけだと計算量的には何の改善にもなっていないが、辺を張った後に集合をクリアするようにすれば、全体でO(NlogN)でできるようになる。今は連結性だけに興味があるので、ノード内に同連結成分のものは2つ以上必要ないからである。
右端をSegment Treeに追加する際には、その座標を含むノード全ての集合に追加するだけで良い。
構築したグラフ上でDFSすれば、連結成分が求まる。ここまで全てO(NlogN)で可能。
だが、このグラフでは二部グラフ判定はできない。ここからは二部グラフ判定の方法を考える。
連結成分を求めるのに使ったSegment Treeを活用したい。
ここで、各ノード内の集合について、「右端を追加する時に集合に入ったもの①」と、「辺を張る時に便宜上加えたもの②」に頂点を分けることを考える。②は高々1つしか存在しないことに注意。
この時、①と②の色は必ず異なり、①同士、②同士の色は必ず等しくなることが分かる。辺を張る時、両端がどっちに属しているかは明らかなので、各辺ごとに両端の色の関係が分かる。
この情報によって、DFSをする際に、色を決めてしまうことができる。ただし、ここで決めた色は必要条件にすぎないことに注意。
後は十分性をチェックすればよく、色が決まっていることから、実際にシミュレーションすれば良い。
全体でO(NlogN)で解けた。
実装
Segment Treeのノードにはvectorを乗せている。
定数倍で落ちたので、グラフの辺数を抑えるために、UnionFindを使って必要な辺だけ張るようにした。
atcoder.jp
感想
考察中にいい性質(使えるとは言っていない)が色々見つかって迷走してしまった。
こういう問題を短時間で解ける日は来るのかな......
