AGC 064

Sun, Mar 30, 2025

https://atcoder.jp/contests/abc064

A. i i’s

https://atcoder.jp/contests/agc064/tasks/agc064_a

2025/3/30 解説読んでもどうやったらその思考になるのかわからず。結局諦めた

2025/5/10 リベンジして AC

$N$, $N-1$ を交互に以下の様にまずは並べる.

$$N, N-1, N, \cdots, N-1, N$$

次に $N-2$ を両端と、残りの $N-4$ 個を左から条件を満たす部分に挿入していく。数字を decrement しつつ操作を続け、最後に $2$ は両端、1 は左端か右端のどちらかにおけば条件を満たす数列を構成できる。

$N \leq 1000$ のため愚直に $O(N^2)$ のシミュレーションをしても実行時間制限に間に合う。

より直感的に説明すると $N, N-1$ となっているところに $N-2$ を挿入して $N, N-2, N-1$ となっても $N-2, N-1$ という並びができるおかげで次の $N-3$ を挿入できる場所ができるから、数字を挿入することによって次の数字を挿入できる場所の数は減らない。

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

    int N;
    cin >> N;

    vint ans(N * 2 - 1, N);
    for (int i = 1; i < N * 2 - 1; i += 2) {
        ans[i] = N - 1;
    }

    for (int i = N - 2; i >= 1; i--) {
        vint tmp;
        int cnt = i;
        int m = ans.size();
        tmp.push_back(i);
        cnt--;
        rep(j, m) {
            tmp.push_back(ans[j]);
            if (cnt > 1 && j + 1 < m && tmp.back() != i && ans[j + 1] != i && abs(tmp.back() - i) <= 2 && abs(ans[j + 1] - i) <= 2) {
                tmp.push_back(i);
                cnt--;
            }
        }
        if (cnt)
            tmp.push_back(i);
        swap(tmp, ans);
    }
    print(ans);
}