これは手こずったけどまぁ本番解けてよかったと思うかな…。
http://codeforces.com/contest/763/problem/C
解法
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; }
まとめ
本番「総和から公差求められないかな、やっぱり無理か」と思っていたので、二乗和を併用する解法はすごいと思った。