Codeforces #773 : Div1 B. Repetitions Decoding

いまいちだった回。
https://codeforces.com/contest/1641/problem/B

問題

整数列がtandem repeatであるとは、同じ数列を2回繰り返した形になっているものをいう。
今N要素の整数列Aが与えられる。以下の手順を2*N*N回まで繰り返しAをtandem repeatを繰り返したものにできるか。できるならその手順を答えよ。

• 数列の任意の位置に、同じ値cを2つ隣同士に挿入する

解法

"1 a b c 1 a x y"のように、先頭1と同じ要素が途中に出てきたとする。その際、1の後ろを、1の手前と先頭と同じになるように値を追加する。
例えばこの例だと"1 a b c 1 a b c c b x y"となる。
そうするとprefixの"1 a b c 1 a b c"がtandem repeatになるのでこれらを取り除ける。

この手順では、最悪O(N)手かければAのうち2要素をTandem Repeatとして切り離せるので、全体でO(N^2)手で全体をtandem repeatの連結にできる。

int T,N;
ll A[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<pair<int,int>> op;
		vector<int> pat;
		deque<int> Q;
		FOR(i,N) {
			cin>>x;
			
			Q.push_back(x);
		}
		int len=0;
		while(Q.size()) {
			x=Q.front();
			Q.pop_front();
			vector<int> C;
			while(Q.size()) {
				y=Q.front();
				if(x==y) break;
				C.push_back(y);
				Q.pop_front();
			}
			if(Q.empty()) {
				Q.push_front(0);
				break;
			}
			len+=C.size()+2;
			/*
			cout<<x<<"!";
			FORR(c,C) cout<<c<<" ";
			cout<<":";
			FORR(q,Q) cout<<q<<" ";
			cout<<endl;
			*/
			pat.push_back(2*(C.size()+1));
			Q.pop_front();
			FORR(c,C) {
				if(Q.size()&&Q.front()==c) {
					Q.pop_front();
					len++;
				}
				else {
					op.push_back({len,c});
					len++;
					Q.push_front(c);
				}
			}
			
			
		}
		
		if(Q.size()) {
			cout<<-1<<endl;
		}
		else {
			cout<<op.size()<<endl;
			FORR2(a,b,op) {
				cout<<a<<" "<<b<<endl;
			}
			cout<<pat.size()<<endl;
			FORR(a,pat) cout<<a<<" ";
			cout<<endl;
		}
		
		
	}
}

まとめ

本番結構苦戦してるな…。