ARC 183

Sat, Jul 5, 2025

A. Median of Good Sequences

https://atcoder.jp/contests/arc183/tasks/arc183_a

$N$ の偶奇によって場合分けする。

(i) $N$ が偶数のとき

長さ $NK$ の数列の順列のうち、前半半分は先頭の数字が $1, 2, \cdots, N/2$ から始まるものであり、後半半分は $N/2, \cdots, N$ から始まるものである。求めるものは先頭の文字が $N/2$ のうち、辞書順で一番最後のものなので残りの数字を降順に並べて出力する

(ii) $N$ が奇数のとき

対称性より先頭の $K$ 個は $\floor{(N+1)/2}$ を $K$ 個並べる。残りの数字を使って辞書順で真ん中になるものは $\floor{(N+1)/2}-1$ を一つ追加し、残りの数字を降順に並べる。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;
    vint rem(N + 1, K);
    rem[0] = 0;
    vint ans;
    int x = (N + 1) / 2;
    if (N % 2 == 0) {
        ans.push_back(x);
        rem[x]--;
    } else {
        rep(i, K) {
            ans.push_back(x);
        }
        rem[x] = 0;
        x--;
        if (rem[x] > 0) {
            ans.push_back(x);
            rem[x]--;
        }
    }

    for (int x = N; x >= 1; x--) {
        rep(i, rem[x]) ans.push_back(x);
    }
    print(ans);
}