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

AGC004 B - Colorful Slimes

問題

agc004.contest.atcoder.jp

考察

まず、魔法を使う回数はN回未満で事足ります。
N回以上だと2週目に入ってしまい、それであればちょうど1週したタイミングで飼えば良いからです。
また、飼うタイミングを調整することにより、魔法を何回掛けるかを調整することができます。

これにより、「魔法を何回掛けるか」を決めると、それぞれで最小の所要時間が求まります。

T回魔法を掛けるとすると、それぞれの色のスライムで0〜T回の所要時間が必要です。
が、実際には魔法は0〜T回のどれかで掛けられるので、どの色のスライムを飼えばいいかが分かれば良いです。
T回魔法を掛けるので、色iであればi-Tまでの色を飼えます。
この値は、直前の結果(魔法を1回少なく掛けている)を利用することで O(N)で計算できます。

このように、それぞれの色で最適な(元の)色を決め( O(N))、魔法の回数を全通り試す( O(N))ことで、全体として O(N * N)で答えが求まります。

コード

int main() {
    ll N, x;
    cin >> N >> x;
    vll a(N);
    rep(i, N)
        cin >> a[i];

    const ll INF = 1ll << 60;

    vvll dp(N, vll(N + 1, INF));
    rep(i, N) {
        dp[i][0] = a[i];
    }
    rep(i, N) {
        REP(j, 1, N + 1) {
            int prev_j = (i - j + N) % N;
            dp[i][j] = min(dp[i][j - 1], a[prev_j]);
        }
    }

    ll ans = INF;
    rep(j, N + 1) {
        ll tmp = 0;
        rep(i, N)
            tmp += dp[i][j];
        chmin(ans, tmp + (ll) j * x);
    }

    cout << ans << endl;

    return 0;
}