AGC004 B-Colorful Slimes

【問題】
agc004.contest.atcoder.jp

【考察】
最初、魔法で色を変えられるスライムは 1 匹だけと勘違いしてて、各色のスライムごとに元になるスライムをどの色にすればコストが最小になるかを計算するコードを書いたんですが、サンプルの 2 で落ちて誤読に気づきました。そこでちょっと考えてみると、魔法の唱える回数を k と固定すると、全てのスライムは、適当な瞬間に召喚することにより、自分の色から k 遡るまでの任意の色のスライムから遷移できることが分かります。あとはその中で最小のコストを見つけて、その色のスライムから遷移すると決めればいいです。
最小値を計算するのにセグツリを使ったら結構実行時間が危なくなった。

【コード】

// RMQ のコードは省略
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,x;
	cin>>n>>x;
	RMQ rmq(n);
	REP(i,n) {
		ll a;
		cin>>a;
		rmq.update(i,a);
	}
	ll ret=INF*INF;
	REP(i,n+1) {
		ll cost=x*i;
		REP(j,n) {
			ll c=INF*INF;
			c=min(c,rmq.query(max(0ll,j-i),j+1));
			if(j-i<0) c=min(c,rmq.query(n-(i-j),n));
			cost+=c;
		}
		ret=min(ret,cost);
	}
	cout<<ret<<endl;
}

【使ったアイデア】
思いつくまで頑張る。

【得た知見】
何か重要な値を固定したり、要素を独立に考えたりすると見通しがよくなることがある（結構ある？）。