Codeforces #709 Div1 : B. Playlist

ずいぶん苦労してるな…。
https://codeforces.com/contest/1483/problem/B

問題

N個の曲の一覧があり、それぞれのジャンル番号が指定される。
これらの曲を、一覧を巡回して演奏する。
その際、最後2曲のジャンル番号が素でない場合、最後にうたった曲が、一覧から削除される。

曲の一覧が変化しなくなるまでつづけたとき、削除される曲番号を列挙せよ。

解法

隣接要素が互いに素でない要素の列を、dequeにまとめて管理しよう。
そうすると曲の一覧はdequeのリストで管理できる。
deque内の要素は互いに削除されないので削除処理を行う必要もない。
あとは、dequeとdequeの境界の部分だけ愚直にシミュレートしていこう。

int T,N;
int A[101010];


deque<int> D[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) D[i].clear();
		deque<int> Q;
		vector<int> R;
		int pre=-1,fir=-1;
		FOR(i,N) {
			cin>>A[i];
			
			if(pre==-1) {
				Q.push_back(i);
				D[i].push_back(i);
				pre=fir=i;
			}
			else {
				if(__gcd(A[pre],A[i])==1) {
					R.push_back(i);
					pre=-1;
				}
				else {
					D[fir].push_back(i);
					pre=i;
				}
			}
		}
		if(pre!=-1) {
			Q.push_front(Q.back());
			Q.pop_back();
		}
		
		int up=0;
		while(up<Q.size()+1) {
			up++;
			if(Q.size()==1) {
				x=Q.front();
				//cout<<"!"<<D[x].size()<<endl;
				if(__gcd(A[D[x].back()],A[D[x][0]])==1) {
					R.push_back(D[x][0]);
					D[x].pop_front();
					if(D[x].empty()) Q.pop_front();
					up=0;
				}
				else {
					break;
				}
			}
			else if(Q.size()>1) {
				x=Q.front();
				Q.pop_front();
				y=Q.front();
				//cout<<"!!"<<D[x].size()<<" "<<D[y].size()<<endl;
				if(__gcd(A[D[x].back()],A[D[y][0]])==1) {
					R.push_back(D[y][0]);
					D[y].pop_front();
					if(D[y].empty()) Q.pop_front();
					up=0;
					Q.push_back(x);
				}
				else {
					while(D[x].size()) D[y].push_front(D[x].back()),D[x].pop_back();
					up=0;
				}
			}
		}
		
		
		cout<<R.size();
		FORR(r,R) cout<<" "<<r+1;
		cout<<endl;
		
	}
}

まとめ

曲なんて設定ではなく普通に数列を操作する設定だとダメなのかな。
数列を巡回する感じが表現しにくいのかな。