Codeforces #838 : Div2 G. Unequal Adjacent Elements

解法から問題考えてそうな問題。
https://codeforces.com/contest/1762/problem/G

問題

N要素の整数列Aが与えられる。
以下を満たす1～Nの順列Pが構築できるか。可能なら一例を示せ。

• P[i-2]＜P[i]
• A[P[i-1]]!=A[P[i]]

解法

もしNが奇数で、Aの再頻出な値が(N+1)/2回出てくる場合、Pは一択である。P[2i]にA[P[2i]]がその再頻出な値が出てくるように配置しなければならない。
Aを、そのような部分列に分割してそれぞれPを考え、最後に連結していけばよい。

int T,N,A[303030];
int F[302020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	FOR(x,T) {
		cin>>N;
		FOR(i,N) F[i]=0;
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
			F[A[i]]++;
		}
		FOR(i,N) if(F[i]>(N+1)/2) break;
		if(i!=N) {
			cout<<"NO"<<endl;
			continue;
		}
		int L=0;
		vector<ll> ret(N);
		while(L<N) {
			int LV=A[L];
			vector<int> C[2];
			int cur=L;
			C[A[cur]!=LV].push_back(cur);
			cur++;
			while(cur<N&&(C[0].size()!=C[1].size()))  {
				C[A[cur]!=LV].push_back(cur);
				cur++;
			}
			
			if(C[0].size()==C[1].size()) {
				C[1].pop_back();
				FOR(i,C[0].size()) ret[L+i*2]=C[0][i];
				FOR(i,C[1].size()) ret[L+1+i*2]=C[1][i];
				L+=C[0].size()+C[1].size();
				continue;
			}
			if(C[0].size()==C[1].size()+1&&cur==N) {
				FOR(i,C[0].size()) ret[L+i*2]=C[0][i];
				FOR(i,C[1].size()) ret[L+1+i*2]=C[1][i];
				L+=C[0].size()+C[1].size();
				continue;
			}
			
			//巻き戻し
			cur=L;
			while(1) {
				if(cur==0||C[0].size()==C[1].size()) {
					sort(ALL(C[0]));
					sort(ALL(C[1]));
					if(C[0].size()!=C[1].size()) {
						ret[cur++]=C[0][0];
						C[0].erase(C[0].begin());
					}
					if(cur&&C[1].size()) {
						//サイズは一緒なので、ぶつかるなら反転
						if(A[ret[cur-1]]==A[C[1][0]]) {
							swap(C[0],C[1]);
						}
					}
					FOR(i,C[0].size()) {
						ret[cur++]=C[1][i];
						ret[cur++]=C[0][i];
					}
					break;
				}
				//1手戻す
				cur--;
				C[A[ret[cur]]!=LV].push_back(ret[cur]);
			}
			break;
		}

		cout<<"YES"<<endl;
		FORR(a,ret) cout<<a+1<<" ";
		cout<<endl;
	}
}

まとめ

解法はわかっても実装の細かいところがめんどい。