想定解と別方針として、より一般性の高い次の問題に帰着して解く方法を考えます:

\(1\) 以上 \(N\) 以下の値を取るの \(M\) 個の区間 \([l_i,r_i]\) が与えられます。各 \(i = 1,2,\dots,K\) について \(i\) 個以下の区間の和集合の最大サイズを求めてください。

問題の帰着

数列 \(A\) を降順にソートします。各 \(l=1,2,...,n\) に対して \(\frac{A_l}2 < A_r\) であるような \(r\) の最大値を求め、得られた \(n\) 個の \([l,r]\) のペアを区間の集合とします (このような \([l,r]\) の集合は尺取法によって \(O(N)\) 時間で計算することが可能です)。

このとき以下が成り立ちます:

得られた区間の集合において \(i\) 個の区間の和集合のサイズを \(s\) 以上にできるとき、およびそのときに限り高橋くんが \(i\) 回、青木くんが \(n - s\) 回の操作で作業を完了できる。

問題文の手順に照らし合わせると区間同士が重なる選び方が許されませんが、この条件は外しても問題ありません(重ならない区間の選び方で和集合のサイズがそれ以上になるものが存在することから示すことができます)。

得られた集合に対して \(i\) 個の区間の和集合の最大サイズが \(N - k\) 以上になるような最小の \(i\) およびそのときの \(N - (\text{最大サイズ})\) が答えとなります。

また、一度の高橋くんの除草で最大高さが半分以下になることから、考える必要のある区間の個数 \(M\) は高々 \(O(\log{\max(A)})\) 個であることが分かります。

区間の和集合の最大サイズの計算

次のようなDPを考えます:

\(\mathrm{dp}[i,j] = {}\)( \(i\) 個の区間で \(1,2,\dots,j\) の値のうち被覆できる最大個数 )

このとき \(\mathrm{dp}[i,j]\) は次の3つのいずれかの最大値になります:

• \(\mathrm{dp}[i,j-1]\)
• \(j\) を右端に持つ ( \(j=r\) である) 区間 \([l,r]\) に関して
  • \(\underset{0≤k≤l-1}{ \max}\mathrm{dp}[i-1,k] + (j-l+1)\)
  • \(\underset{l≤k} { \max \ }\mathrm{dp}[i-1,k] + (j - k)\)

これらはそれぞれ

• \(j\) を右端とする区間を用いない場合
• \(j\) を右端とする区間を用いる場合で
  • この区間と重なる区間がそれより左に存在しない場合
  • この区間と重なる区間がそれより左に存在する場合

に対応します。最後の更新式に関しては、包含されるような区間は存在しないとしても最適値が変化しないことから正当性を確かめることができます。

2つの最大値はそれぞれ \(\mathrm{dp}[k]\) の値そのものと、\(\mathrm{dp}[k]-k\) の値をそれぞれ管理するセグメント木を持つことで高速に計算できます。

以上よりこの問題は \(O(KN + KM\log(N))\) 時間で解くことができます。

(不備がありましたらtwitterのリプライ・DMなどでお教えくださるとありがたいです)