Colorful Slimes [AGC 004 : B]

問題

http://agc004.contest.atcoder.jp/tasks/agc004_b

N色のスライムがいる。
この時、2種類の操作を選んで行う。

• 飼っていない色iのスライムを選んで飼う。a[i]秒かかる
• 全ての飼っているスライムの色iが色i+1になる。x秒かかる

2 <= N <= 2 * 10^3
1 <= a[i], x <= 10^9

帰納的考察(Editorial見た)

1. Nが10^3オーダーなので、解法はO(N^2)だろう
2. 色変換の操作の回数でも全探索するのかなー
3. おわり

――壁――

4. 解説にこんな一節がある

例えば，K = 2 で最終的に色 3 のスライムが欲しい場合，次の 3 通りの方法があります．
• 魔法を唱える → 魔法を唱える → スライム 3 を捕まえる
• 魔法を唱える → スライム 2 を捕まえる → 魔法を唱える
• スライム 1 を捕まえる → 魔法を唱える → 魔法を唱える

5. なるほど以外の言葉が見当たらない
6. なので、k回色変換するとするとa[i-k]～a[i]の最小値を全てのiについて計算する
7. その和とk*xを足すとk回色変換した時の最短時間
8. これの最小値が答え
9. 最小値を見つける所も解説に書いてあってなるほどって感じ
10. セグメントツリー使っても間に合う

実装

http://agc004.contest.atcoder.jp/submissions/870285

#define INF 1LL<<60
typedef long long ll;
int N;
ll x;
int a[2010];
int b[2010];
//-----------------------------------------------------------------
int main() {
	cin >> N >> x;
	rep(i, 0, N) cin >> a[i];
 
	ll ans = INF;
	rep(i, 0, N) b[i] = a[i];
	rep(k, 0, N) {
		ll can = k * x;
		
		rep(i, 0, N) b[i] = min(b[i], a[(i - k + N) % N]);
		rep(i, 0, N) can += b[i];
 
		ans = min(ans, can);
	}
	cout << ans << endl;
}