第4回 ドワンゴからの挑戦状 本戦 : C - XOR ピラミッド

AtCoderはなんかピラミッド好きな印象がある。
https://dwacon2018-final-open.contest.atcoder.jp/tasks/dwacon2018_final_c

問題

長さが奇数、すなわち(2N-1)の形で表現できる数列が与えられる。
要素数が3以上のとき、(2N-1)要素の数列Aから、(2N-3)要素の数列BをB[i]=A[i]^A[i+1]^A[i+2]として作る操作を行う。
この操作を数列長が1になるまで繰り返すとき、最終的に残る値は何か。

解法

長い数列から短い数列を求めるのではなく、逆に短い数列から長い数列を求めることを考えよう。
S={1}から、T[i]=A[i-2]^A[i-1]^A[i] (範囲外は0とする)の要領で長さが2長い数列を作るとする。

これを問題の入力と同じ(2N-1)要素になるまで繰り返したとする。
この時、問題の解は、この数列で1となる要素を抜き出してxorする値と同じである。
ここで、後者の数列はフラクタルを成している。
すなわち偶数回処理を繰り返し長さが(4M+1)の形で表せるとき、その(0-indexで)偶数番目の要素を抜き出したものは長さ(2M+1)の時点の要素と等しい。
この事実を用いて、数列に対し2ずつ長さを増減させるのではなく、一気に約半分にすることを考える。

改めて元の数列Aを考える。

• 長さが(4M+1)で表せるとき、偶数要素を抜き出したAに置き換える。
• 長さが(4M+1)で表せない、1回だけ処理を行う。

Aは入力の時点でRLEされた状態で与えられる。
上記２処理もこの状態のまま行うようにしよう。

int M;
vector<pair<int,ll>> V;

vector<pair<int,ll>> half(vector<pair<int,ll>> V) {
	vector<pair<int,ll>> R;
	int x=1;
	FORR(v,V) {
		R.push_back({v.first,(v.second+x)/2});
		x ^= v.second%2;
	}
	return R;
}

vector<pair<int,ll>> step(vector<pair<int,ll>> V) {
	int i;
	vector<pair<int,ll>> R;
	FOR(i,V.size()) {
		if(V[i].second>2) R.push_back({V[i].first,V[i].second-2});
		if(V[i].second>=2 && i<V.size()-1) R.push_back({V[i+1].first,1});
		if(V[i].second>=1 && i<V.size()-1) {
			if(V[i+1].second>=2) R.push_back({V[i].first,1});
			else if(i<V.size()-2) R.push_back({V[i].first^V[i+1].first^V[i+2].first,1});
		}
	}
	return R;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	FOR(i,M) {
		cin>>x>>y;
		if(V.empty() || V.back().first!=x) V.push_back({x,0});
		V.back().second+=y;
	}
	
	while(1) {
		if(V.size()==1 && V[0].second==1) {
			cout<<V[0].first<<endl;
			return;
		}
		
		vector<pair<int,ll>> V2;
		ll L=0;
		FORR(v,V) if(v.second) {
			if(V2.empty() || V2.back().first!=v.first) V2.push_back({v.first,0});
			V2.back().second+=v.second;
			L+=v.second;
		}
		
		if((L-1)%4==0) {
			V=half(V2);
		}
		else {
			V=step(V2);
		}
		
	}
	
}

まとめ

逆向きに考えるのは思いつかなかった。