AtCoder ARC #084 : E - Finite Encyclopedia of Integer Sequences

最初真面目に考えたけど、結局実験ゲーで解いた。
https://beta.atcoder.jp/contests/arc084/tasks/arc084_c

問題

整数K,Nが与えられる。
1～Kの整数1～N個からなるすべての数列を辞書順にソートしたとき、中央に来るものを答えよ。

解法

Kが偶数の場合、全体の数列の組み合わせが偶数なので、先頭を(K/2)とする最後の数列を作ればよい。
つまり先頭が(K/2)でその後Kを(N-1)個並べればよい。

Kが奇数の場合、大よそceil(K/2)をN個並べれば中央に近そうだが、実際試してみると、長さがN未満の数列の影響でちょっとずれる。
実際ceil(K/2)をN個並べたものから(N/2)個巻き戻せば解になる。

int N,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>N;
	
	if(K%2==0) {
		FOR(i,N) {
			_P("%d%c",(i==0)?(K/2):K,(i==N-1)?'\n':' ');
		}
		return;
	}
	
	vector<int> V;
	FOR(i,N) V.push_back(K/2+1);
	FOR(i,N/2) {
		if(V.back()==1) V.pop_back();
		else {
			V.back()--;
			while(V.size()<N) V.push_back(K);
		}
	}
	
	FORR(c,V) cout<<c<<" ";
	cout<<endl;
	
	
}

まとめ

愚直に求めようとすると結構大変そう。