Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AGC004-B 「Colorful Slimes」 (400)

問題リンク

概要

 N色のスライムを、以下の2つの操作によって全色揃えたい。

  •  iのスライムを捕獲する。これには時間が a_iかかる。
  • 今持っている全てのスライムの色を1増やす。色 Nのスライムは色1になる。これには時間が xかかる。

全色揃えるのにかかる時間の最小値を求めよ。

制約

  •  2 \leq N \leq 2,000
  •  1 \leq a_i \leq 10^9
  •  1 \leq x \leq 10^9

解説

(以下、添字は Nを法とする。)

まず解の上限は \sum a_iとなる。全部のスライムを捕獲すればいい。

あとは色を変える操作を行うケースだが、この操作の回数 tを全探索することにする。

結論を言ってしまうと、このとき色 iのスライムを手に入れるのにかかる時間は min(a_{i - t}, a_{i - t + 1}, \dots , a_i)と見なせる。 これを実現する操作は以下の通り。

  •  iについて、 (a_{i - t}, a_{i - t + 1}, \dots , a_i)で最小なものが a_{i - k_i}だったとする。 (0 \leq k_i \leq t)
  • このとき j tから1まで走らせて以下のような操作を行う。
    •  k_i = jなる全ての iについて、スライム a_{i - j}を捕獲する。
    • 色を変える。
  • 最後に k_i = 0なる iについて、スライム a_iを捕獲する。

逆に k \gt tのとき、どうやっても a_{i - k} a_iに変えることはできないのでこれが最適となる。

あとは実装だが、各 tについて毎回 min(a_{i - t}, a_{i - t + 1}, \dots , a_i)を調べていると計算量は O(N^3)でTLEとなる。 実際これは無駄が大きく、最小値が更新されうるのは a_{i - t} \lt min(a_{i - t + 1}, \dots , a_i)のときのみである。 これを利用して、それまでの最小値を保持するような配列を用意すれば比較対象が a_{i - t}だけになるので、計算量が O(N^2)に落ちて無事通る。

実装例

#include <iostream>
using ll = long long;
using namespace std;

int main() {
    ll N, x;
    cin >> N >> x;

    ll a[N], c[N];
    // c[i] = min(a[i - t], a[i - t + 1], ... , a[i]) 
    
    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
        c[i] = a[i];
        ans += a[i];
    }

    for (ll t = 1; t < N; ++t) {
        ll cost = t * x;
        for (int i = 0; i < N; ++i) {
            c[i] = min(c[i], a[(i + N - t) % N]);
            cost += c[i];
        }
        ans = min(ans, cost);
    }

    cout << ans << endl;
    return 0;
}

 Nを法とする数の扱いに注意。引き算では負の値に対して除算を行う可能性があるので、上のように一旦 Nを足して正にすると上手くいく。

ちなみに、セグ木を使えば区間最小値を O(\log N)で出せるので愚直にやっても間に合ったりする。

感想

  • 説明が難しすぎる。
  • かといって図を書くのもまた難しい。