kmjp's blog

競技プログラミング参加記です

Codeforces #395 Div1 C. Timofey and remoduling

これは手こずったけどまぁ本番解けてよかったと思うかな…。
http://codeforces.com/contest/763/problem/C

問題

素数Mに対し、0~(M-1)のうち異なるN個A[i]が与えられる。
このN個を並べ替え、(mod Mに関し)等差数列を構成できるか。
できるなら初項と公差を応えよ。

解法

N=1,M-1,Mのいずれかのときは公差1の解が自明に見つかるので省略。
以下2≦N≦M-2の場合を考える。

公差を総当たりすることを考える。
A[0]の次がA[i]だとすると、公差をd=A[i]-A[0]と仮定したとき、…A[0]-2d, A[0]-d, A[0], A[0]+d, A[0]+2d…と、A[0]を含む公差dの数列が最大何要素あるかを求める。
これがN要素とれるならその公差dが解である。
(A[0]が末尾の場合は考えなくてもよい。A[0]が末尾の場合、公差をM-dにとればA[0]が初項に来る数列を考えられる。)

問題は、上記判定はNとMの値が近い場合、O(N^2)かかることである。

仮にAが初項p・公差dのN要素の数列p, p+d, ... , p+(N-1)d (mod M)で構成されるなら、残りのp+Nd, p+(N+1)d, … , p+(M-1)dはAと共通部分を持たない。
よって、後者を満たすp,dを求められればよい。

上記どちらかを判定することで、N要素か(M-N)要素のうち少ない方が等差数列か判定すればよくなる。
判定対象がMの半分以下であれば、大概の場合N要素たどる前に条件を満たさないことが判定できるので、高速に処理できる。(O(N*sum(1/N))位?)

ほかにも、Aの総和と二乗和から公差を求める手法もあるようだ。

ll N,M;
ll A[101010];
bitset<1<<20> BS[1024];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M>>N;
	FOR(i,N) cin>>A[i], BS[A[i]>>20][A[i]&((1<<20)-1)]=1;
	
	if(N==1) {
		cout<<A[0]<<" "<<0<<endl;
		return;
	}
	if(N==M-1) {
		FOR(i,M) if(BS[0][i]==0) {
			cout<<(i+1)%M<<" "<<1<<endl;
			return;
		}
	}
	if(N==M) {
		cout<<0<<" "<<1<<endl;
		return;
	}
	sort(A,A+N);
	
	if(2*N<M) {
		for(i=1;i<N;i++) {
			int d=A[i]-A[0];
			
			ll L,R,cur=A[0];
			for(R=0;R<N-1;R++) {
				cur+=d;
				if(cur>=M) cur-=M;
				if(BS[cur>>20][cur&((1<<20)-1)]==0) break;
			}
			cur=A[0];
			for(L=0;L+R<N-1;L++) {
				cur+=M-d;
				if(cur>=M) cur-=M;
				if(BS[cur>>20][cur&((1<<20)-1)]==0) break;
			}
			if(L+R>=N-1) {
				ll P=((A[0]-L*d)%M+M)%M;
				cout<<P<<" "<<d<<endl;
				return;
			}
		}
	}
	else {
		int le=M-N;
		FOR(i,M) BS[0][i]=1;
		FOR(i,N) BS[0][A[i]]=0;
		int first=-1;
		FOR(i,M) if(BS[0][i]==1) {
			if(first==-1) {
				first=i;
			}
			else {
				ll d=i-first;
				
				ll L,R,cur=first;
				for(R=0;R<le-1;R++) {
					cur+=d;
					if(cur>=M) cur-=M;
					if(BS[0][cur]==0) break;
				}
				cur=first;
				for(L=0;L+R<le-1;L++) {
					cur+=M-d;
					if(cur>=M) cur-=M;
					if(BS[0][cur]==0) break;
				}
				if(L+R>=le-1) {
					ll P=((first-L*d)%M+M)%M;
					cout<<(P+le*d)%M<<" "<<d<<endl;
					return;
				}
			}
		}
		
		
		
	}
	cout<<-1<<endl;
	
}

まとめ

本番「総和から公差求められないかな、やっぱり無理か」と思っていたので、二乗和を併用する解法はすごいと思った。