Official

F - Domination Editorial by maroonrk_admin


自身の右上領域に赤い石がないような赤い石だけを考えます. 一般性を失わず,\(RX_1<RX_2<\cdots<RX_N\)\(RY_1>RY_2>\cdots>RY_N\) を仮定します.

まず,青い石の配置が与えられたとき,以下の \(2\) つの条件は同値になります.

  • 各赤い石の右上領域に \(K\) 個以上の青い石がある.

  • 青い石を \(K\) グループに適切に分割することで,各赤い石の右上領域にそれぞれのグループの青い石がある .

下→上は明らかです. 上→下は,各青い石がカバーできる赤い石の範囲が区間になっていることを考えると証明できます.(詳細は省略しますが帰納法が回ります)

次に,\(K=1\) の時に問題を解く方法を考えます.

まず,何らかの与えられた \(1\leq l \leq r \leq N\) について,赤い石 \([l,r]\) をカバーするコストについて考えます. これを以下のような問題に帰着してみます.

  • \(X\) 軸上,\(Y\) 軸上を移動できるトークンを考える. このトークンは,\(X\) 軸上を正/負の方向に距離 \(1\) 進むにはコスト \(1/0\) かかり,\(Y\) 軸上を正/負の方向に距離 \(1\) 進むにはコスト \(0/1\) かかるとする. また,各青い石 \(j\) につき,\(Y\) 軸の座標 \(BY_j\) の地点から,\(X\) 軸の座標 \(BX_j\) にジャンプできるとする. このとき,\(Y\) 軸上の座標 \(RY_l\) から \(X\) 軸上の座標 \(RX_r\) へと向かう最短コストが,赤い石 \([l,r]\) をカバーするコストになる.

これが正しい答えを出すことは明らかです.

ここで,各 \(1 \leq i \leq N-1\) について,\(X\) 軸上の座標 \(RX_i\) の点から,\(Y\) 軸上の座標 \(RY_{i+1}\) へのコスト \(0\) の辺を貼ってみます. すると,\(RY_1\) から \(RX_N\) への最短路が,\(K=1\) の場合の答えになっていることがわかります.

一般の \(K\) については,単に同じグラフで流量 \(K\) の最小費用流を求めればよいです.この時,青い石に対応する辺だけ容量を \(1\) にします. この正当性は,最初に述べた同値条件から従います.

計算量は全体で \(O(K(N+M)\log (N+M))\) です.

posted:
last update: