Weed [AtCoder Beginner Contest 203（Sponsored by Panasonic） F]

https://atcoder.jp/contests/abc203/tasks/abc203_f

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/abc203/submissions/23075597

まずAはソートしておこう。
これはよくあるテクであるが、ソート可能な配列はソートしておく。

何に気付くべきか

この問題は1つ重要な部分に気が付くことができるかがターニングポイントになる。

まず、青木君の操作を無視して、K=0のときを考えてみよう。
この時行われる操作は一意的になるので単純にシミュレーションすることで必要な高橋君の操作回数が分かる。
これで色々な場面を想定して性質を探すと、面白いことに気が付く。

1回操作を行うと残っている草の高さの最大値は半分以下になる。
最大値は10⁹なので、半分以下を繰り返していき、0になるのに必要な回数を考えると30回が上限となる。
よって、青木君が改良しない場合であっても高橋君の操作の最大値は30回という極端に小さい値になる。

この性質が役に立つ。

動的計画法へ

これを考慮することでDPにつなげることができる。

dp[i][takahashi] := ソート済みの庭の草がi個処理済みであって、高橋君の操作回数がtakahashi回であるときの、青木君の最小操作

このようにソート済みの庭の草を小さい方から処理していくことにする。
遷移は2つ。

• 青木君が草を抜く
  • dp[i][takahashi] + 1 -> dp[i+1][takahashi]
• 高橋君が抜く
  • dp[i][takahashi] -> dp[nxt][takahashi + 1]
  • nxtはi番目の草を抜くときに最適となる最大の高さとして選択される草の番目

2番目の遷移が少しややこしい。
i番目の草を高橋君の操作で抜こうとした場合は、どの草が最大の高さとして選択されるかが選択肢としてあり得る。
このすべての試すのは間に合わないので、最も最適なものだけ遷移として試すことにする。
i番目の草を抜くためにはA[i]*2未満の草のうちを最大のものを抜くのが最適。
こうすることでより多くの草を抜くことができる。

答えるときはK≦dp[N][takahashi]を満たす最小のtakahashiを使って答えよう。

int N, K, A[201010];
int dp[201010][50];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);

    rep(i, 0, N + 1) rep(takahashi, 0, 40) dp[i][takahashi] = inf;
    dp[0][0] = 0;
    rep(i, 0, N) rep(takahashi, 0, 40) if(dp[i][takahashi] != inf){
        chmin(dp[i + 1][takahashi], dp[i][takahashi] + 1);
        int nxt = lower_bound(A, A + N, A[i] * 2) - A;
        chmin(dp[nxt][takahashi + 1], dp[i][takahashi]);
    }

    rep(takahashi, 0, 40) if (dp[N][takahashi] <= K) {
        printf("%d %d\n", takahashi, dp[N][takahashi]);
        return;
    }
}