Codeforces #941 : Div1 D. Missing Subarray Sum

こちらは本番中に解けず…。
https://codeforces.com/contest/1965/problem/D

問題

N要素の回文を成す整数列Aを当てる問題である。
Aの連続部分列の総和の集合のうち、1つ除いたものが与えられる。
Aの全要素を特定せよ。

解法

Aが回文なので、部分列の始点と終点が数列の中心から見て対称的な位置にある場合、その和は奇数回登場し得る。
それ以外のケースは、必ず偶数回登場する。

前者の和がすべてわかれば、Aは復元できる。
そこで、1つ除かれたものが前者か後者か判定し、それによって分岐する。

• 1つ除かれたものが対称的な位置にあるものの場合
• 1つ除かれたものが非対称的な位置にあるものの場合

いずれも、残りの奇数回登場した数列の和から数列を復元し、そこから再び部分列の和を列挙しよう。
列挙したものと入力を比較すると、その差分から残り1要素を特定できる。

int T;
int N;
ll S[1010101];
ll A[1010];
vector<ll> hoge(vector<ll> V,int num) {
	deque<int> D;
	if(num%2==0) {
		D.push_back(V[0]/2);
		D.push_back(V[0]/2);
	}
	else {
		D.push_back(V[0]);
	}
	int i;
	for(i=1;i<V.size();i++) {
		D.push_back((V[i]-V[i-1])/2);
		D.push_front((V[i]-V[i-1])/2);
	}
	V.resize(num);
	FOR(i,num) V[i]=D[i];
	return V;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	FOR(k,T) {
		cin>>N;
		int M=N*(N+1)/2;
		map<int,int> U;
		FOR(i,M-1) {
			cin>>S[i];
			U[S[i]]++;
		}
		sort(S,S+M-1);
		
		int NO=(N+1)/2;
		vector<ll> Os;
		FOR(i,M-1) {
			if(Os.size()&&Os.back()==S[i]) Os.pop_back();
			else Os.push_back(S[i]);
		}
		
		vector<ll> V;
		if(Os.size()==NO-1) {
			//奇数を削った
			V=hoge(Os,N-2);
			
			ll ma=0;
			FOR(x,V.size()) {
				ll s=0;
				for(y=x;y<V.size();y++) {
					s+=V[y];
					U[s]--;
					if(U[s]==0) U.erase(s);
				}
				ma=max(ma,s);
			}
			ll u=U.rbegin()->first;
			if(u>ma) {
				V.push_back(u-ma);
				V.insert(V.begin(),V.back());
			}
			else {
				u=S[M-2]-u;
				ll s=0;
				
				FOR(x,V.size()) {
					
					if(s+V[x]>u) {
						ll y=V[x];
						if(N%2&&x==N/2-1) {
							V.insert(V.begin()+x,0);
							V[x+1]=(y-2*(u-s));
							V[x]=(u-s);
							V.insert(V.begin()+N-1-x,0);
							V[N-1-x]=V[x];
							V[N-2-x]=V[x+1];
						}
						else {
							V.insert(V.begin()+x,0);
							V[x+1]=y-(u-s);
							V[x]=u-s;
							V.insert(V.begin()+N-1-x,0);
							V[N-1-x]=V[x];
							V[N-2-x]=V[x+1];
						}
						
						break;
					}
					s+=V[x];
				}
			}
			
			
			
		}
		else {
			//奇数以外を削った
			int ok=0;
			FOR(i,Os.size()) if((Os.back()-Os[i])%2) {
				Os.erase(Os.begin()+i);
				ok=1;
				break;
			}
			if(ok==0) {
				V=hoge(Os,N+2);
				FOR(x,V.size()) {
					int s=0;
					for(y=x;y<V.size();y++) {
						s+=V[y];
						U[s]--;
					}
				}
				int rem=0;
				FORR2(a,b,U) if(b) rem=a;
				rem=2*rem-S[M-2];
				FOR(i,Os.size()) if(Os[i]==rem) {
					Os.erase(Os.begin()+i);
					break;
				}
			}
			V=hoge(Os,N);
		}
		
		
		FOR(i,N) cout<<V[i]<<" ";
		cout<<endl;
	}
}

まとめ

考え方はともかく、実装は割とめんどいな。