ARC084 E : Finite Encyclopedia of Integer Sequences(800)

作成日:2017.11.05
最終更新日:2017.11.05

問題概要

問題本文

 $1$以上$K$以下の整数からなる長さ$1$以上$N$以下の整数列の集合を考える。 この集合に含まれる数列の個数を$X$とする時、辞書順で$X/2$(切り上げ)番目の数列を求めよ。
制約
$1 \leq K,N \leq 3 \times 10^5$

考え方

 $K$が偶数の時、数列の初項が$K/2$以下のものとそれ以外のものは同数あることから、答えは初項が$K/2$、あとの$N-1$項が$K$の数列である。
 以下では$K$が奇数の時を考える。 両端から同数だけ取り除いても「真ん中」は変わらないことから、答えの初項は$(K+1)/2$である。 第2項以降も同様に考えていくのだが、初項の時とは異なり今見ている項が存在しない数列も1つだけある。 このことを考慮しなければ「真ん中」は$(K+1)/2$を$N$個並べた数列$A$になる。 しかし実際には考慮する必要がある。 無視した数列は$N-1$個であり、すべて$A$よりも辞書順で小さいものである。 先頭に$x$個要素を加えると「真ん中」は$x/2$(切り上げ)個先頭にずれる。 この2つのことから、辞書順で$A$の$N/2$(切り捨て)個前のものが答えであると分かる。
1つ前の数列を求める時のならし計算量は$O(1)$であることから、この方針で解くことができる。

ソースコード

マクロ等はこちら

const int MC = 300010;
int K,N;
int ans[MC];

int main(){
	cin >> K >> N;
	if(K%2==0){
		cout << K/2;
		repp(i,1,N) cout << ' ' << K;
		cout << endl;
	} else {
		fill(ans,ans+N,(K+1)/2);
		int z = N-1;
		repp(i,0,N/2){
			if(ans[z] > 0){
				--ans[z];
			} else {
				--ans[z-1];
				ans[z] = K;
				if(ans[z-1]==0) --z;
				else z = N-1;
			}
		}
		repp(i,0,N){
			cout << ans[i] << (ans[i+1]==0?'\n':' ');
			if(ans[i+1]==0) break;
		}
	}
	return 0;
}

解法まとめ

 $K$が偶数の時は初項が$K/2$、あとの$N-1$項が$K$の数列が答えである。(8-10行)
 $K$が奇数の時は$(K+1)/2$が$N$個並んだ数列より辞書順で$N/2$(切り捨て)個前の数列が答えである。(12-23行)

ARC084の他の問題 C D F

自己紹介

プログラミングとか合成音声とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

最終更新日:2023.03.05

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

寄付モドキ

0冂から10000冂まで
詳しくはこちら