ARC 162

Mon, May 12, 2025

A. Ekiden Race

https://atcoder.jp/contests/arc162/tasks/arc162_a

人 $i$ が順位下げた場合、人 $i$ よりも早く走った人がいることになるので復路でのタイムが最も早かったことにはならない。また順位を下げていなくても以下の図1 の Y のように誰かに抜かされていたらその人も復路でのタイムが最も早かったことにはならない。これらの人を除くと位置関係は図2 のように往路、往復での相対的な位置関係が変わらない人だけが残る。これらの人の復路でのタイムが同じでも位置関係は保たれるのでこのような条件を満たす人たちの数を数えれば良い。

位置関係図1

┌──────────────────┐
│                  │
│                  ▼
X  Y  Z────►Z  Y   X
   │           ▲
   │           │
   └───────────┘

図2

┌───────────┐
│           │
│           ▼
X  Y        X  Y
   │           ▲
   │           │
   └───────────┘

┌──────┐
│      │
│      ▼
X      X  Y     Y
          │     ▲
          │     │
          └─────┘

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

    auto cal = []() -> void {
        ll N;
        cin >> N;
        vll P(N);
        rep(i, N) cin >> P[i];

        vector<pair<ll, ll>> ps;
        rep(i, N) {
            ps.emplace_back(i + 1, P[i]);
        }
        reverse(all(ps));

        ll l = -1, r = INF;
        ll ans = 0;
        for (auto [before, after] : ps) {
            if (before < after) continue;
            if (before < l && r < after) continue;
            ans++;
            l = before, r = after;
        }
        cout << ans << '\n';
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

B. Insertion Sort 2

https://atcoder.jp/contests/arc162/tasks/arc162_b

自力 AC. 1時間近く掛かった。

実験により 2 1 がダメ、3 2 1 もダメなことから転倒数が奇数の場合は無理だと予想がついた。また、2つの数字を移動させるということなので転倒数の偶奇も移動によって変わらない。

構成法について、小さい数字から順に左に移動させていくことを考える。目当ての場所に移動させるには後述の通り多くとも 2 回の移動で済むため、$N \leq 10^3$ という制約では $2 \times 10^3$ 回以下の操作で必ず昇順に並べることができる。

$P_1, \cdots, P_p$ までは昇順に並んでおり、次に移動させるべき数字 $p+1$ が $k$ 番目にあるとする。このとき $k < N$ と $k = N$ で場合分けする。

$k < N$ のとき、$i = k$, $j = p$ とすることで、目当ての数字を $p+1$ 番目に移動させることができる。

$k = N$ のとき、$i = k-2$, $j = N$ とし、目当ての数字より左にある 1,2 個を末端に移動させることで $k < N$ の状態にすることができる。ここで $P$ は偶置換であるので $p+1$ が右端にあるとき、左2つは $p+1$ よりも大きい数字である。

以上より、目当ての数字は目当ての場所に2回以下の操作で移動させることができる。

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

    int N;
    cin >> N;
    vint P(N);
    rep(i, N) {
        cin >> P[i];
        P[i]--;
    }

    // 転倒数をチェック
    {
        vector<pair<int, int>> ids;
        rep(i, N) {
            ids.emplace_back(P[i], i);
        }
        sort(all(ids));
        fenwick_tree<int> fw(N);
        int tento = 0;
        for (auto [_, i] : ids) {
            tento += fw.sum(i, N);
            fw.add(i, 1);
        }
        if (tento % 2 == 1) {
            yesno(false);
            return;
        }
    }

    vector<pair<int, int>> histories;
    int cnt = 0;
    int nx = 0;
    int sorted_pos = -1;
    while (true) {
        if (is_sorted(all(P)))
            break;
        cnt++;
        int pos = distance(P.begin(), find(all(P), nx));
        if (pos < N - 1) {
            sorted_pos++;
            histories.emplace_back(pos + 1, sorted_pos);

            vint tmpP;
            rep(i, sorted_pos) {
                tmpP.push_back(P[i]);
            }
            tmpP.push_back(P[pos]);
            tmpP.push_back(P[pos + 1]);
            rep2(i, sorted_pos, N) {
                if (i == pos || i == pos + 1)
                    continue;
                tmpP.push_back(P[i]);
            }
            nx++;
            swap(tmpP, P);
        } else {
            vint tmpP;
            pos -= 2;
            rep(i, N) {
                if (i == pos || i == pos + 1)
                    continue;
                tmpP.push_back(P[i]);
            }
            tmpP.push_back(P[pos]);
            tmpP.push_back(P[pos + 1]);
            histories.emplace_back(pos + 1, N - 2);
            swap(tmpP, P);
        }
    }

    yesno(true);
    cout << cnt << endl;
    for (auto [i, j] : histories)
        cout << i << ' ' << j << endl;
}