まず、問題の制約下で青木君の抜いた本数に関わらず \(\lfloor\log_2 (\max(A_i))\rfloor+1\) 回以下の操作で終了させられることを示します。 ( ただし、 \(\lfloor x \rfloor\) で \(x\) 以下の最大の整数を表します。) これは一度の操作で残っている草の高さが半分以下になる事から示せます。 \(A_i<2^{\lfloor\log_2 (\max(A_i))\rfloor+1}\) より、 \(\lfloor\log_2 (\max(A_i))\rfloor\) 回操作を行ってまだ草が残っているとすると、その草の高さは \(2\) 未満ですからすべての草の長さは \(1\) です。よって \(\lfloor\log_2 (\max(A_i))\rfloor+1\) 回目の操作で終了します。

さて、動的計画法でこの問題を解くことを考えます。 まず先に草の長さを昇順にソートしておきます。 すなわち \(A_1\leq A_2\leq\cdots \leq A_N\) であるとします。

\(dp[i][j]={}\)(草 \(1\) から草 \(i\) までが最初に庭に生えていると考えた時、\(j\) 回以下で操作を終了するために青木君が抜かなくてはならない最小の本数)

とし、これを求めることを考えます。このとき上で示した事実と\(\lfloor\log_2 (10^9)\rfloor+1=30\) より、 \(j\) については \(0\leq j\leq 30\) の範囲を 考えればよいです。
次に初期値と遷移を考えます。まず、\(i=0\) ならば草は最初から \(0\) 本ですから、 \(dp[0][j]=0\) です。 \(i\geq 1\)に対しては定義からまず \(dp[i][0]=i\) であり、 \(j\geq 1\) について、草 \(i\) を青木君が抜いた場合の最小値は \(dp[i-1][j]+1\) です。一方、草 \(i\) を青木君が抜かなかった場合は、 \(1\) 度目の操作の前に残っている最も高い草の長さは \(A_i\) であるので、高さが \(\frac{A_i}{2}\) 以下の草のうち最も番号が大きいものを \(f(i)\) ( \(\frac{A_i}{2}<A_1\) のときは\(f(i)=0\) )として、\(dp[f(i)][j-1]\) で与えられます。よって、 \(dp[i][j]=\min(dp[i-1][j]+1,dp[f(i)][j-1])\) と書けます。

あとは \(f(i)\) が求まればこの動的計画法は完成します。 しかしこれは定義より \(f(i)\leq f(i+1)\) であることを用いれば 、\(f(i+1)\) は \(j=f(i)\) から始めて \(\frac{A_i}{2}<A_{j+1}\) である限り \(j\) を \(1\) ずつ増やしていき、そうでないときその時点での \(j\) を \(f(i+1)\) の値として定める事で求まり、これを繰り返して求めてゆけば、 全体で \(O(N)\) で求めることができます。 また、各 \(i\) に対して二分探索で \(O(\log N)\) で求め全体で \(O(N\log N)\)で求めることもできます。これでも十分高速です。

元の問題に戻って求めたいものを考えると \(dp[n][j]\leq K\) となる最小の \(j\) が高橋君の最小の操作回数であり、 このときの\(dp[n][j]\) の値が青木君が抜かなくてはならない最小の本数です。これで求めたいものがすべて求まりました。

動的計画法のパートは遷移はそれぞれ \(O(1)\) で出来るので全体で\(O(N\log (\max(A_i)))\) となり、 \(f(i)\) を \(1\) つ目の \(O(N)\) の方法 で求めたとすると全体で \(O(N\log (\max(A_i)))\) で求まります。 これで十分高速にこの問題を解く事が出来ました。

C++による実装例:

#include <bits/stdc++.h>

using namespace std;

#define N 200010
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
	int n, k;
	int a[N];
	int dp[N][31];
	int b[N];
	cin >> n >> k;
	rep(i, n)cin >> a[i];
	sort(a, a + n);
	int cur = 0;
	rep(i, n) {
		while (a[cur] <= (a[i] / 2))cur++;
		b[i] = cur;
	}
	rep(j, 31)dp[0][j] = 0;
	rep(i, n) {
		dp[i + 1][0] = dp[i][0] + 1;
		rep(j, 30) {
			dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, dp[b[i]][j]);
		}
	}
	rep(j, 31) {
		if (dp[n][j] <= k) {
			cout << j << " " << dp[n][j] << endl;
			return 0;
		}
	}
	return 0;
}