部分点１部分点制約：N ≦ 8
並び替えを全部試せばいいです。
部分点２部分点制約：N ≦ 16
巡回セールスマン問題に落としてbitDPでできます。
部分点３部分点制約：答えが 0 かどうかだけを判定すれば良い
これが想定通りに解ければ満点はすぐそこです。
ただ、よく分からずに貪欲を頑張って考えるとこの部分点までは取れたりするようです。
まず、(A,B) = (INF,1) のトンネルを新たに作り、トンネルをループ状に繋げられるようにする問題だと考えたほうが少し考えやすくなります。
INFはmax(A_i)で十分です。
各トンネルは「体が A_i 以下なら入れる」ではなく、「ちょうど A_i なら入れる」＋「好きなタイミングで何回でも体を 1 大きくすることができる」と考えたほうが考えやすくなります。
A_i, B_i を数直線上にプロットし、A_i→B_iの有向辺を張ります。
このとき、以下のようなサイクルが存在すれば答えは 0 となります。
- トンネルの辺をちょうど１回ずつ通る（下図の赤辺）
- 数直線を右に進むのは自由（下図の緑辺）
例えば、1-緑->2-緑->3-赤->1-緑->2-赤->5-緑->6-赤->8-赤->1 というサイクルがあるので、このケースの答えは 0 です。
トンネルを頂点ではなく辺にしたことにより、ちょっとオイラー路っぽい問題になりました。
しかし、緑辺を通る回数がよく分からないのでまだオイラー路問題ではないです。
さて、各緑辺を通る回数は自由なのですが、実は一意に定まります。
各頂点に、赤辺の「入次数ー出次数」を書き込み、左から累積和を取れば、各緑辺を通るべき回数が求まります。
緑辺を通るべき回数が負になった場合はその時点で答えは 0 ではないと言えます。
これで完全に（有向）オイラー路問題に帰着できました。
あとはオイラー路の条件「入次数＝出次数」と「連結である」をチェックすれば良くなりました。
次数条件は緑辺を通る回数を求めた時点で自動的に満たされているので、連結性のみを判定すれば良いです。
連結性条件は無向グラフだと思って判定しても大丈夫なので、適当にやればOKです。
あらかじめ座標圧縮をしておかなければならない点だけ注意して下さい。
満点スモールライトについて考えなければなりません。
スモールライトは下図の青辺のような、数直線を左に進む辺に対応します。
この問題は、青辺を追加する本数を最小化する問題ということになります。
青辺が必要になる状況は以下の２通り考えられます。
- 「緑辺を使う回数」が負になる箇所を相殺する
- 青辺と緑辺をセットで追加して２つの連結成分をつなげる
まずは負の箇所の相殺をします。このとき、相殺した箇所は連結になる点に注意して下さい。
次に、全体を連結にすることを考えます。
連結成分の形は下図のように結構複雑な形になることがあるので単純には行きません。
数直線上で隣接する頂点の間に青辺（＋逆向きの緑辺）を張ることにより、それらを連結に出来ます。
さてここで、連結性判定時には辺を無向だと思って良いことを思い出すと、以下のように辺を張ったグラフのMSTを求めればいいことになります。
- 赤辺と緑辺と負を相殺するための青辺（コスト＝０）
- 数直線上で隣接する頂点間を結ぶ青辺（コスト＝距離）
これで解けました。
まとめハミルトン路がオイラー路になり、MSTになりました。
open all / close all
generated by indenter
