実装を柔軟にしたい

問題概要

$N$ 体のスライムがあって、初期状態では、それぞれの色は $1, 2, \dots, N$ となっている。以下の操作を繰り返すことで全てスライムを消滅させたい。そのために必要なコストの最小値を求めよ。

色 $i$ のスライムを消滅させる (コストは $a_{i}$ )
スライムの色をスライドさせる (コストは $x$ 、色 $i$ のスライムは色 $i+1$ になり、色 $N$ のスライムは色 1 になる)

制約

$2 \le N \le 2000$

考えたこと

一瞬、各スライムごとに独立に

そのスライム以降の色に +x, +2x, +3x, ... としていって、その最小値を求める (色変化が数珠なので例によって二週させる)

という風にすればよさそうに思ってしまった。しかし、色変化は全ての残スライムに共通なのだ。よって、むしろ

スライムの色変化の最大値を固定する (色変化コストは固定)
その最大値を超えない範囲で、各スライムがどこまで色変化をすればよいかを求める

という風にすればよさそうだ。

高速化

このままでは $O(N^{3})$ の計算量がかかってしまう。つまり

色変化最大値を固定
各スライムについて
何色分変化させるのが最適なのかを求める

ということで、それぞれについて $O(N)$ を掛け算して $O(N^{3})$ を要してしまう。しかし、色変化最大値を増やすたびに累積 max をとる要領で更新していけば $O(N^{2})$ にできる。具体的には

色変化最大値が $k$ であるとき、初期色 $i$ のスライムを消滅させる最小コストは $\min(a_{i}, a_{i+1}, \dots, a_{i+k})$ で求められる
$\min(a_{i}, a_{i+1}, \dots, a_{i+k})$ の更新は $k$ の変化に応じて差分更新を行っていく

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long INF = 1LL<<60;
int N;
long long X;
vector<long long> A;

long long solve() {
    long long res = INF;
    for (int i = 0; i < N; ++i) A.push_back(A[i]);
    vector<long long> bmin(N, INF);
    for (int k = 0; k < N; ++k) {
        long long tmp = 0;
        for (int i = 0; i < N; ++i) {
            chmin(bmin[i], A[i+k]);
            tmp += bmin[i];
        }
        chmin(res, tmp + X*k);
    }
    return res;
}

int main() {
    while (cin >> N >> X) {
        A.resize(N);
        for (int i = 0; i < N; ++i) cin >> A[i];
        cout << solve() << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 004 B - Colorful Slimes (青色, 400 点)

問題概要

制約

考えたこと

高速化