AtCoder ARC #077 : E - guruguru

しょうもないミスを連発した。
http://arc077.contest.atcoder.jp/tasks/arc077_c

問題

1～mの値を取るカウンタがある。
カウンタは1回順送りボタンを押すと1増加する。ただしカウンタがmの状態でボタンを押すと1になる。

さて、ここでお気に入り値xを定めていたとする。
お気に入りボタンを1回押すと、カウンタの値がxになる。
お気に入りボタンは何度も利用できるが、xの値を途中で変更することはできない。

数列Aが与えられる。
初期のカウンタ値がA[0]として、A[i]を順に経由するようにしたい。
お気に入り値を最適に定めたとき、全カウンタ値を経由する最小ボタン押下回数はいくつか。

解法

A[i]＜A[i+1]の例を考える。
お気に入り値を無視すればカウンタ値A[i]→A[i+1]の遷移には(A[i+1]-A[i])回かかる。
ただし、お気に入り値xが[A[i]+2,A[i+1]]の範囲である場合、A[i+1]-x+1回で済み、押下数が削減できる。

ということは、xが[A[i]+2,A[i+1]]の範囲なら(A[i+1]-x+1回)、それ以外なら(A[i+1]-A[i])かかる。
よってSegTree等で区間に定数値またはindexに線形な値を加算できるデータ構造を再現できれば、各iに対し同様の加算を行うことで各xに対するボタン押下回数が求められる。
あとはそのうち最小値を答えればよい。

区間または線形値の合算はSegTreeやBITで行うこともできるが、自分は(xの2次式が登場するので)累積和を2回取る形式で対応した。
なお、A[i]＞A[i+1]のケースは周回の面倒なので、カウンタ値を3周分シミュレートした。

int N,M;
int A[202020];
ll sum=0;
ll dif[302020];
ll tot[302020];
ll ret[302020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i], A[i]--;
	FOR(i,N-1) {
		x=A[i];
		y=A[i+1];
		if(y<x) y+=M;
		sum += y-x;
		if(x+1<y) {
			dif[x+2]++;
			dif[y+1]--;
			tot[y+1]+=y-x-1;
			dif[M+x+2]++;
			dif[M+y+1]--;
			tot[M+y+1]+=y-x-1;
		}
	}
	
	
	ll mi=1LL<<60;
	FOR(i,3*M) {
		if(i) {
			dif[i]+=dif[i-1];
			tot[i]+=tot[i-1];
		}
		tot[i]-=dif[i];
		mi=min(mi,sum+tot[i]);
	}
	cout<<mi<<endl;
	
}

まとめ

方針はあってたのに、しょうもない3WAで順位を落としまくってつらい。