問題
解法
赤い石は RX_1 < RX_2 < ... < RX_N , RY_1 > RY_2 > ... > RY_N となっているとして良いです。
このとき、各青い石がカバーするのは区間になります。
青い石を1個ずつ見ていきます。(石 t と呼ぶ)
パターン1
x座標もy座標も自分より大きいような赤い石がない場合
この場合は、既にいくつか(0個の場合もある)の赤い石をカバーしていて、y座標を増やすと区間の左端が左へ、x座標を増やすと区間の右端が右へ進んでいき、独立に考えることができます。
パターン2
x座標もy座標も自分より大きいような赤い石がある場合
そのような赤い石の集合をSとします。
この場合は、初期時点では赤い石を1つもカバーしていません。
石 t が赤い石を1個以上カバーするように操作するのが最適なら、石 t はSを全てカバーするとして良いことがいえます。
証明:
適当にカバーしている区間を縮めて、全ての赤い石のカバーされる回数がちょうどKになるようにしておく。a, a+1 をSの要素として、石 t がカバーする区間が [l , a] という解が最適だとする。このとき、a+1 はカバーしているが a はカバーしていないような石が存在するが、その石が追加で [l , a] もカバーするようにして石 t は 1 つもカバーしないようにしても解が悪化することはない。(証明終わり)
このことを利用すると、だいたいパターン1と同様に考えられるようになります。
Sの要素のうち x 最大のものを s としたとき、青い石 t を 赤い石 s のところまで移動させるコストを最初に払うと、石 s での更新処理を適切に行うことでパターン1のように扱えます。
最後に、ここからどう解くかを考えます。
dp[i][a][b] = i 番目の赤い石までは条件を満たしていて、y座標を増やしてカバーするのに使う青い石の借りが a 個あり、x座標を増やしてカバーするのに使える青い石が b 個あるときの最小コスト と定義して更新タイミングを頑張ると N=M として O(K^3 N + NlogN) で解くことができました。
(aを増やす、bを増やす、a+b+(最初からカバーされている個数) >=K かをチェック、aを減らす、bを減らす、パターン2の処理、の順)でやったのですが、スライド最小値を使わないで O(K^4 N + NlogN) にした方が速かった
提出
