Codeforces #240 Div1 A. Mashmokh and Numbers

CF240は不参加。
出ていたらABDは1発回答でレート上がったかもな。
Cも1発ではないにしろ自力で解答できた。
http://codeforces.com/contest/414/problem/A

問題

N要素のdistinctな正整数配列A[i]を考える。
この配列のスコアは偶数iに対しA[i]とA[i+1]の最大公約数の総和である。

数値N,Kが与えられたとき、N要素でスコアがKとなる配列Aを構成せよ。

解法

distinctな正整数の最大公約数は最少1である。
よってまず以下のコーナーケースは除外しておく。

• N==1の時はどんなA[0]でもスコアは0である
• N>=2なら最小スコアはN/2なので、KがN/2未満なら構成不可。

それ以外、すなわちN>=2かつK>=N/2の場合を考える。
単純に最初の2要素を最大公約数K-(N/2)-1とし、残り(N-2)要素を各スコア1となるように取ればよい。
よって先頭2要素をK-(N/2)-1, 2*(K-(N/2)-1)にして、それ以降2*(K-(N/2)-1)から1つずつインクリメントしていけばdistinctになる。

void solve() {
	int f,i,j,k,l,x,y;
	int N,K;
	
	cin>>N>>K;
	
	if(N==1) {
		if(K==0) return _P("1\n");
		else return _P("-1\n");
	}
	
	if(K-N/2<0) return _P("-1\n");
	
	_P("%d %d ",K-N/2+1,2*(K-N/2+1));
	j=2*(K-N/2+1)+1;
	FOR(i,N-2) _P("%d ",j++);
	_P("\n");
	
}

まとめ

コーナーケースさえ気を付ければ後は簡単。