Codeforces #248 Div1 A. Ryouko's Memory Note

CF248は不参加。どうも難易度が高かったようで…。
http://codeforces.com/contest/434/problem/A

問題

M要素の整数列A[i]が与えられ、各要素は1～Nの間である。
この数列のコストは、隣接項の差の絶対値の総和(abs(A[i+1]-A[i])の総和)である。

A[i]に対しある数値xを１つ選択し、A[i]中のxをすべてyに置換できるとする。
その際数列のコストを最小化せよ。

解法

まず、xを選択するために各A[i]=xにおいて隣接するA[i-1]とA[i+1]を列挙しておき、各xにおいて隣接する数値の配列V[x]を求めておく。

各xについて、コストの最小化を試みる。
x→yにしたときのコスト削減量は、(sum(abs(x-V[x][i])))-(sum(abs(y-V[x][i])))であり、後者の項が最小となるyを求めればよい。
yの候補としてはV[x][i]のいずれかが考えられるので、y=V[x][i]を各iについて総当たりし、sum(abs(y-V[x][i]))の最小値を求めればよい。
sum(abs(y-V[x][i]))の値はV[x][i]の累積和を取っておけばO(1)で求められる。

V[x]のサイズの総和は2(M-1)であり、xの候補はN通りなのでO(N+M)で処理可能。

int N,M,A[100001];
vector<int> V[100001];
ll S[100002];
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,M) cin>>A[i];
	
	ll ret=0;
	FOR(i,M) if(i>0 && A[i]!=A[i-1]) V[A[i]].push_back(A[i-1]), ret+=abs(A[i]-A[i-1]);
	FOR(i,M) if(i<M-1 && A[i]!=A[i+1]) V[A[i]].push_back(A[i+1]), ret+=abs(A[i]-A[i+1]);
	ret/=2;
	
	ll ma=0;
	FOR(i,N+1) {
		sort(V[i].begin(),V[i].end());
		S[0]=0;
		ll cm=0;
		FOR(j,V[i].size()) S[j]=((j>0)?S[j-1]:0)+V[i][j], cm+=abs(i-V[i][j]);
		FOR(j,V[i].size()) {
			ll dd=(j+1)*(ll)V[i][j]-S[j]+(S[V[i].size()-1]-S[j])-(V[i].size()-(j+1))*(ll)V[i][j];
			ma=max(ma,cm-dd);
		}
	}
	cout << ret-ma << endl;
}

まとめ

Aとしては若干ややこしい問題。