kmjp's blog

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

Codeforces #166 Div2. C. Secret

さて、Div2 CはDiv1 A相当なので、ここからはDiv1にも登場する難易度になる。
http://codeforces.com/contest/271/problem/C

問題

1~Nで構成される数列をK個の数列に分ける。
このとき、各数列は等差数列にならないようにした数列の分け方の一例を答える。

解法

まず前提として、各数列の項目数が2以下だと必ず等差数列になるので、N>=3Kでなければならない。
各数列の項目数が3以上として、このとき色々な分け方がある。

自分の手法は、まず先頭の1~Kを1つシフトして2,3,4…,K,1番目の数列の先頭要素にする。
K+1以降は、1,2,...,K番目の数列に順に割り当てる。
すると、各数列2項目目以降は等差数列になるけど、先頭だけは等差にならない。

int K,N;

void solve() {
	int f,r,i,j,k,l,x,y;
	
	GET2(&N,&K);
	if(N/K<3) {
		_P("-1\n");
		return;
	}
	
	FOR(x,N) {
		if(x<K) _P("%d ",1+(x+1)%K);
		else _P("%d ",(x%K)+1);
	}
	_P("\n");
	
	return;
}

まとめ

Codeforcesはこういう、「色々やり方があるけどうまく分類してね」問題が多い気がする…。