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

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

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

実装を柔軟にしたい

問題へのリンク

問題概要

 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}) にできる。具体的には


  1. 色変化最大値が  k であるとき、初期色  i のスライムを消滅させる最小コストは  \min(a_{i}, a_{i+1}, \dots, a_{i+k}) で求められる
  2.  \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;
    }
}