Codeforces #654 Div2 E2. Asterism (Hard Version)

なんで今回Fのupsolveがやたら多いんだろ？
https://codeforces.com/contest/1371/problem/E2

問題

N要素の整数列Aが与えられる。
整数xに対し、f(x)は以下のように定める。

Aの各要素に対し、ある順番でxを突き合わせる。xがAの値以上ならxはインクリメントし、Aの値未満なら処理を終了する。
xを全要素に突き合わせられるような、突き合わせ順の数がf(x)。

ここで、f(x)が素数pで割り切れないようなxを列挙せよ。

解法

xを突き合わせていくとき、終了しない突き合わせ候補がpの倍数となるようなxは不可である。
の初期値をmax(A)-N以上max(A)まで総当たりし、そのようなタイミングがないものを列挙しよう。

int N,P;
int A[101010];
int num[202030];
set<int> cand[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P;
	map<int,int> num;
	FOR(i,N) {
		cin>>A[i];
	}
	sort(A,A+N);
	FOR(i,N) {
		if(A[i]<A[N-1]-N) A[i]=A[N-1]-N;
		num[A[i]]++;
	}
	
	for(i=A[N-1]-N;i<=A[N-1]+N;i++) {
		num[i+1]+=num[i];
		cand[((num[i]-i)%P+P)%P].insert(i);
	}
	
	vector<int> R;
	for(x=A[N-1]-N;x<=A[N-1];x++) if(x>=1) {
		y=(P-x%P)%P;
		auto it=cand[y].lower_bound(x);
		if(it!=cand[y].end() && *it<x+N) continue;
		R.push_back(x);
	}
	cout<<R.size()<<endl;
	FORR(r,R) cout<<r<<" ";
	cout<<endl;
	
}

まとめ

問題がわかりにくいなぁ…。