AGC 058

Tue, May 13, 2025

A. Make it Zigzag

https://atcoder.jp/contests/agc058/tasks/agc058_a

0-index で考える。 $i \equiv 0 \mod 2$ のときに、$P_i$, $P_{i+1}$, $P_{i+2}$ の大小関係は以下の4通りにに分けられる。

Type A: $P_i < P_{i+1} < P_{i+2}$
Type B: $P_i > P_{i+1} > P_{i+2}$
Type C: $P_i > P_{i+1} < P_{i+2}$
Type D: $P_i < P_{i+1} > P_{i+2}$

Type A のとき、 $\mathrm{swap}(P_{i+1}, P_{i+2})$ を行うことで $P_i < P_{i+1} > P_{i+2}$ を実現できる

Type B のとき、 $\mathrm{swap}(P_i, P_{i+1})$ を行うことで $P_i < P_{i+1} > P_{i+2}$ を実現できる

Type C のとき、 $P_i > P_{i+2}$ ならば $\mathrm{swap}(P_i, P_{i+1})$ を行い、$P_i < P_{i+2}$ なら $\mathrm{swap}(P_{i+1}, P_{i+2})$ をすることで $P_i < P_{i+1} > P_{i+2}$ を実現できる

Type D のときは何もする必要ない

$i = 2N-1$ のときは、$P_{i} > P{i+1}$ ならば $\mathrm{swap}(P_i, P_{i+1})$ を行う.

$i \equiv 0 \mod 2$ のときに上記の操作をしていれば $i \equiv 1 \mod 2$ のときは操作を必要はない。よって、$N$ 回以下の操作で条件を満たすことができる。

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

    int N;
    cin >> N;
    vint P(N * 2);
    rep(i, N * 2) cin >> P[i];

    vint ans;
    for (int i = 0; i < N * 2 - 1; i += 2) {
        if (i == N * 2 - 2) {
            if (P[i] > P[i + 1]) {
                swap(P[i], P[i + 1]);
                ans.push_back(i);
            }
        } else {
            if (P[i] < P[i + 1] && P[i + 1] < P[i + 2]) {
                swap(P[i + 1], P[i + 2]);
                ans.push_back(i + 1);
            } else if (P[i] > P[i + 1] && P[i + 1] > P[i + 2]) {
                swap(P[i], P[i + 1]);
                ans.push_back(i);
            } else if (P[i] > P[i + 1] && P[i + 1] < P[i + 2]) {
                if (P[i] > P[i + 2]) {
                    swap(P[i], P[i + 1]);
                    ans.push_back(i);
                } else {
                    swap(P[i + 1], P[i + 2]);
                    ans.push_back(i + 1);
                }
            }
        }
    }
    for (int& x : ans)
        x++;
    cout << ans.size() << endl;
    print(ans);
}