kojingharangの日記

Codeforces #412 Mister B and PR Shifts (Div2 D, Div1 B)

18:51 |

• [1, N] の permutation が与えられる。
• Σ^{N}_{1} |rotate_right(p, j)[i]-i| の最小値とそのときの j を求めよ。
• 2≦N≦10^6

• すごく規則性がありそう
• N^2 で実装して実験くん
• N=10で適当な例を試したら広義単調増加→減少となめらかに変わってそうなので三分探索
• 三分探索初めて書くので非常に怪しい
• WA

(あとで)

• N = 1000 くらいでランダムケースを見てみたら全然なめらかに変わってなかった...
• ちょっとずつずらしたときに某値とその変化量がどれくらい変わるかを最初に O(N) で求めておいて O(N) でちょっとずつずらしていくやり方があるようだ。
• 書いてみるが超絶ムズい...
• なんとか通ったけど +1 -1 とか不等号に等号が付くかとか場合分けとか無限にバグる要素ある。

(accepted in practice)

void solve(ll N, const VI& w, ll& minVar, ll& ans) {
	VI varDiff(N+10), deltaDiff(N+10);
	ll var = 0;
	REP(i, N) {
		VI& dd = deltaDiff;
		// 無限にバグるパート
		if(w[i]>i+1) {
			// 最初 -1 で idx1 のときに +1 になる. また idx3 で -1 になる
			dd[0] += -1;

			int idx1 = w[i]-(i+1);
			dd[idx1] += +2;

			int idx3 = N-(i+1)+1;
			dd[idx3] += -2;
		} else {
			// 最初 +1 で idx1 のときに -1 になる. また idx3 で +1 になる
			dd[0] += +1;

			int idx1 = N-((i+1)-w[i]);
			dd[idx1] += +2;

			int idx3 = N-(i+1)+1;
			dd[idx3] += -2;
		}

		{
			// 回転した瞬間に var が調整される
			int idx = N-(i+1)+1;
			ll v = -(N-(w[i]-1)) + (w[i]-1);
			varDiff[idx] += v;
		}
		var += abs(w[i]-(i+1));
	}
	minVar = var;
	ans = 0;
	ll delta = deltaDiff[0];
	RANGE(i, 1, N) {
		var += varDiff[i] + delta;
		delta += deltaDiff[i];
		if(var<minVar) {
			minVar = var;
			ans = i;
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	ll N;
	while(cin>>N) {
		VI w(N);
		REP(i, N) cin>>w[i];
		ll minVar, ans;
		solve(N, w, minVar, ans);
		cout<<minVar<<" "<<ans<<endl;
	}
	
	return 0;
}

おまけ: メモ

/*
方針:

変化量 = 0
varDiff[i]: i 回目の始めに var が変化する分.
deltaDiff[i]: i 回目の始めに変化量が変化する分
var = rot0でのスコア
loop
	var += 変化量 + varDiff[i]
	変化量 += deltaDiff[i]


5
5 4 3 2 1
での想定動作

0
	-1 -1 -1 -1  1
	deltaDiff
	-1  0  0  0  1
1
	-1 -1  1  1 -1
	deltaDiff
	-1  0  2  0 -2
2
	 1  1  1 -1 -1
	deltaDiff
	 1  0  0 -2  0
3
	 1  1 -1  1  1
	deltaDiff
	 1  0 -2  2  0
4
	 1  1  1  1  1
	deltaDiff
	 1  0  0  0  0

sum
	 1  1  1  1  1



12
8
	12 += -5 +1
6
	8 += -3 +1
6
	6 += -1 +1
8
	6 += +1 +1


0
	p   o
	 p o
	  p
	 o p
	o   p

	delta
		0 -1
		1 -1
		2  1
		3  1
		4  1
		sum 1

1
	 p  o
	  po
	  op
	 o  p
	p

	delta
		0 -1
		1 -1
		2  1
		3  1
		4  1
		sum 1

2
	  p o
	   p
	  o p
	po   
	op

	delta
		0 -1
		1  1
		2  1
		3 -1
		4  1
		sum 1

3
	   po
	   op
	p o  
	 p   
	o p

	delta
		0 -1
		1  1
		2 -1
		3  1
		4  1
		sum 1

4
		p
	p  o 
	 po  
	 op  
	o  p

	delta
		0  1
		1 -1
		2 -1
		3  1
		4  1
		sum 1

*/

ツイートする