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行)