Codeforces #224 Div2. C. Arithmetic Progression

この回は不参加なので練習のみ。
http://codeforces.com/contest/382/problem/C

問題

N個の整数群A[i]が与えられる。
この整数群に１つ整数を追加し、全体を並べ替えて等差数列になるようにしたい。
追加可能な整数を列挙せよ。

解法

地味に場合分けが面倒な問題。
練習でもミスした…。

• N==1の時は、何を加えても等差数列になる。
• Aが全て同じ整数の時、同じ整数のみ追加可能。
• Aがすでに等差数列の場合、先頭要素の１つ前か、最後の要素の１つ後を追加可能。
  • ただし、N==2でかつA[0]とA[1]の差が偶数の場合、A[0]とA[1]の平均値も追加可能。
• Aが基本的に等差数列で、１か所だけ２倍の差がある場合、その２倍の差の真ん中に追加可能。

int N,A[100001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	
	if(N==1) return _P("-1\n");
	if(A[0]==A[N-1]) return _P("1\n%d\n",A[0]);
	if(N==2 && (A[1]-A[0])%2==0) return _P("3\n%d %d %d\n",A[0]-(A[1]-A[0]),A[0]+(A[1]-A[0])/2,A[1]+(A[1]-A[0]));
	
	
	int mi=A[1]-A[0];
	FOR(i,N-1) mi=min(mi,A[i+1]-A[i]);
	x=-1;
	FOR(i,N-1) {
		if(A[i+1]-A[i]==mi) continue;
		else if(A[i+1]-A[i]==2*mi && x==-1) x=i;
		else return _P("0\n");
	}
	if(x==-1) _P("2\n%d %d\n",A[0]-mi,A[N-1]+mi);
	else _P("1\n%d\n",A[x]+mi);
}

まとめ

等差数列・等比数列系の問題、AtCoderでも同じようなのあったな。
いずれも３つ要素があれば初項と項差が確定するのだけど、３つ未満の時は注意だな。