AtCoder Regular Contest 057 B - 高橋君ゲーム

全然解けなくて悲しい…

問題

arc057.contest.atcoder.jp

解法

sum = a1 + a2 + ... + an とします。K < sum の時, 「K 回勝った」というのは「K 回以下勝った」と言い換えても同じであることを示します(K = sum のときは「全部勝つ」という選択肢以外ないのでこれは成り立ちません)。

L < K 回勝った場合を考えます。このとき, 残りの K-L 回の勝つ日をうまく選べば機嫌の良い日が同じかそれ以上になることを示せば良いです。そのための勝つ日の選び方を考えるのですが, N 日間を後ろから見ていき, その日(x 日目とする)が全勝でないなら, 残り勝ち数がなくなるか, その日が全勝になるまで勝ち数を増やします。このようにすると,

• x 日目以前では機嫌の良い日の日数は変わらない
• x+1 日目以降は全勝しているので, 勝率は常に上昇しており, 機嫌が良かったのに悪くなることはない。また, x 日目の勝率は上がるので, x 日目に機嫌が悪かったのが良くなることはあっても良かったのが悪くなることはない。

以上により, 機嫌の良い日は多くなることはあっても少なくなることはありません。以上により, 「K 回勝った」というのは「K 回以下勝った」と言い換えても良いことが分かりました。

これがわかると後は簡単です。

dp[i][j] = (i 日目までに j 回機嫌が良くなるようにするために必要な最低限の勝ち数)とすると,

• i 日目は機嫌を良くしないとすると全敗するのが最適
• i 日目を機嫌よくするとすると最低限勝つのが最適

これで dp[N][ans] <= K となる最大の ans を最後に確認すれば良いです。

K = sum の場合は答えは自明に 1 なので問題なしです。

const int MAXN = 2222;
const int INF = 1e9+7;
int A[MAXN];
int N, K;

int dp[MAXN][MAXN];
int sum[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sum[i+1] = sum[i] + A[i];
    }
    if (sum[N] == K) {
        cout << 1 << endl;
        return 0;
    }
    for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++)
        dp[i][j] = INF;
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j <= i; j++) if (dp[i][j] < INF) {
        // 勝たない
        dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
        // 勝つ
        if (i == 0) {
            dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+1);
        } else {
            ll atleast = (ll)dp[i][j] * sum[i+1] / sum[i] + 1;
            if (atleast <= A[i]+dp[i][j]) {
                dp[i+1][j+1] = min(dp[i+1][j+1], (int)atleast);
            }
        }
    }
    for (int i = N; i >= 0; i--) {
        if (dp[N][i] <= K) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}