Codeforces #833 : Div2 F. Circular Xor Reversal

これ系思いつくまで大変。
https://codeforces.com/contest/1748/problem/F

問題

整数Nが与えられる。
整数列Aの初期値はA[i]=2^iである。
以下の処理を行い、Aを反転せよ。

• iを指定すると、A[i]がA[i]^A[(i+1)%N]に置き換わる。

解法

f(i,j)を、B=(A[i],A[(i+1)%N],A[(i+2)%N],....A[j])に対し、以下を行う処理とする。
m=|B|として、

• B[0]=B[0]^B[m-1]
• B[1]=B[1]^B[m-2]
• ...
• B[(m-1)/2]=B[(m-1)/2]^B[(m+2)/2]

Nが偶数ならf(0,N-1), f(N/2,N/2+1), f(0,N-1)の順、奇数ならf(0,N-1), f((N+1)/2,(N-3)/2), f(0,N-1)の順で行えばよい。
次にfの中身だが、B[x]=B[x]^B[y]を行うには、(y-1),(y-2),....(x)の順で処理した後、(x+1),(x+2),....(y-1)を行うと、B[x]=B[x]^B[x+1]^....^B[y]となる。
これを各xに対し行った後、改めて0,1,2,....(m-1)/2の順で処理すると良い。

int N;
vector<int> V;

void hoge(int L,int R) {
	if(R<L) R+=N;
	int i;
	int OL=L,OR=R;
	while(L<R) {
		for(i=R-1;i>=L;i--) V.push_back(i);
		for(i=L+1;i<R;i++) V.push_back(i);
		L++,R--;
	}
	while(OL<OR-1) {
		V.push_back(OL);
		OL++,OR--;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	hoge(0,N-1);
	if(N%2==0) {
		hoge(N/2,N/2-1);
	}
	else {
		hoge((N+1)/2,(N-3)/2);
	}
	hoge(0,N-1);
	
	cout<<V.size()<<endl;
	FORR(r,V) cout<<r%N<<" ";
	
}

まとめ

こういうパズルっぽい問題どうやると得意になるんだろうな。