読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

ARC057 B - 高橋君ゲーム

ARC DP

難しかった。

問題

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

高橋君はN日間ゲームを行う。i日目にはa_i回のゲームをする。ゲームの結果は勝つか負けるかのどちらかである。

高橋君のi日目の機嫌は勝率によって決まる。i-1日目までの勝率よりi日目までの勝率の方が真に高かったとき、i日目の機嫌がよくなる。そうでないときは悪くなる。ただしi日目までの勝率とは、i = 0 のときは0、そうでないときは (i日目までにゲームに勝った回数) / (i日目までに行ったゲームの回数) である。

高橋君はN日間でちょうどK回ゲームに勝ったことがわかっている。

高橋君の機嫌がよかった日数の最大値は?

制約

1 <= N <= 2000

1 <= a_i <= 500000

0 <= K <= a_1 + ... + a_N

解法

TLE解から考える。それぞれの日について、機嫌がよくなるか悪くなるかの2通りがある。これを全列挙するO(2N)の解法を考えよう。実は機嫌がよくなる日と悪くなる日が決まると、それを実現する最小のKを求めることができる。それは以下のようにして求めた k_i の総和である。(ただし k_i は i 日目に勝つ回数)

  1. i日目に機嫌がよくなるとき: i日目の勝率がi-1日目までの勝率よりぎりぎり大きくなるように k_i を定める
  2. i日目に機嫌が悪くなるとく: k_i = 0

推測として、K 回の勝利で「 A 日機嫌がよくなる」を実現できるなら、 K' (>= K) 回の勝利で 「 A 日以上機嫌がよくなる」を実現することもできそうである。これは実際可能で、勝利回数を後ろから増やしていけばよい。ただしコーナーケースとして、 a_1 + ... + a_N = K のときはこの操作により0日目以外のすべての日の勝率が1となり、機嫌がよくなる日は1日だけとなる。

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
typedef vector<vector<int>> Graph;
// const int inf = 1e9;
const int inf = 2e9;
const int mod = 1e9 + 7;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int N, K;
    cin >> N >> K;
    V a(N + 1);
    rep(i, N) cin >> a[i + 1];

    if (accumulate(all(a), 0) == K) {
        cout << 1 << endl;
        return 0;
    }

    V S = a;
    rep(i, N) {
        S[i + 1] += S[i];
    }
    S[0] = 1;   // 初日の勝率が 0 となるようにするため(0除算を防ぐ)

    VV dp(N + 1, V(N + 1, inf));
    dp[0][0] = 0;
    rep(i, N) {
        rep(j, N) {
            if (dp[i][j] == inf) continue;
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);

            int k = dp[i][j] * a[i + 1] / S[i] + 1;
            if (k > a[i + 1]) continue;
            dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + k);
        }
    }

    int ans = 0;
    rep(j, N + 1) {
        if (dp[N][j] <= K) ans = j;
    }

    cout << ans << endl;

}

最近、論理に頼り過ぎて直感をないがしろにしている気がする。