Finite Encyclopedia of Integer Sequences [AtCoder Regular Contest 084 E]

https://beta.atcoder.jp/contests/arc084/tasks/arc084_c

解説

https://beta.atcoder.jp/contests/arc084/submissions/1744990

公式動画解説を見るのが良い。
ほぼ、それの文字起こしみたいな記事。
　
Kが偶数
最初がK/2、残りのN-1個がKである数列が答え。
　
Kが奇数
ど真ん中っぽい答えは、N個の(K+1)/2が続く数列。
本当の答えはfloor(N/2)回それを戻した数列である。
back関数で1つ数列を戻す。
　
数列を1つ戻すには、基本的には末尾の数を1つ減らすだけ。
しかし、1つ減らした時に0にならなかった場合は、数列の個数がN個になるようにKを追加する。
減らす末尾の添字はどこかにメモって置かないと、毎回末尾を探しているとTLEする。

int K, N;
vector<int> ans;
//---------------------------------------------------------------------------------------------------
int M;
void back() {
    ans[M]--;
    if (0 < ans[M]) {
        rep(i, M + 1, N) ans[i] = K;
        M = N - 1;
    } else M--;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> K >> N;
 
    if (K % 2 == 0) {
        ans.push_back(K / 2);
        rep(i, 0, N - 1) ans.push_back(K);
    } else {
        rep(i, 0, N) ans.push_back((K + 1) / 2);
        M = N - 1;
        rep(i, 0, N / 2) back();
    }
 
    rep(i, 0, N) {
        if (ans[i] == 0) break;
        if (i) printf(" ");
        printf("%d", ans[i]);
    } printf("\n");
}