yukicoder No.1244 Black Segment
問題
N個のセルが並んでおり、1～Nの番号がついていて、すべてのセルが白になっている。
M個のボタンがあり、i番目のボタンを押すと、L_i～R_iのセルの白黒が入れ替わる。
任意の順番で任意の回数ボタンを押すことができるとき、範囲A～Bの部分が黒になっているような状態になるための最小のボタンを押す回数を求めよ。
制約
- 1 <= N <= 10^5
- 1 <= M <= 10^5
- 1 <= A <= B <= N
- 1 <= L_i <= R_i <= N
解法
A～Bの区間はすべて黒になっている必要があるので、「Aまでの部分」から、各ボタンの範囲は連続的につながっている必要がある。
(そうでないと区間内で白の部分ができてしまう)
なので、「Aまでの部分」を固定して、そこから黒が連続している範囲のdpを考える。
dp[i] := 「Aまでの部分」からiまでの部分を黒、i+1～「B+1以降の部分」までが白の状態にするまでの最小操作回数
とすると、
各iについて、ボタンの範囲を使ってdpを更新できる。
(右方向には、黒くするのでdp[i]+1をRのところに更新。左方向には、黒くしていたものを白く戻すので、dp[i]+1をLのところに更新、的なイメージ)
これはダイクストラ法的に計算すればよく、「Aまでの部分」「B+1以降の部分」をs,tでまとめて扱えば、sからスタートして、tまでの最短距離dp[t]を出力すればよい。
