読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

ARC031 C - 積み木

BITの使い方を勉強しなおした。

問題

1, 2, ..., Nの順列がある。この順列の隣り合う2つの要素を並び替えるという操作により数字を山型に並び替えるには最小何回の操作が必要か。

制約

1 <= N <= 105

解法

  • Nをどこに持ってくるかの全通りに対して、左側の反転数 + 右側の反転数 + Nの移動距離 の最小値が答え?→嘘。要素がNをまたぐ場合を考えていなかった。(例: 2, 6, 1, 5, 4, 3 は、1を左端に移すと2回でOK)
  • 最小の要素は一番端に行く。
  • 右端か左端のうちより近い方に移動すればよい。
  • このとき、移動距離はmin(左にあるブロックの個数, 右にあるブロックの個数)
  • ブロックの個数は累積和であり、これを逐次更新したいのでBITを用いる。
  • BITは「位置iにブロックがあるなら1, なければ0」という値を管理するものとするとsum(l, r)が区間(l, r)に含まれるブロックの個数となる。
  • 「最初は全部1だから、BITの配列の各要素を1で初期化しておくってことか!」→大嘘。BITの配列のi番目に入るのは「i番目までの和」なので、ちゃんとaddを呼び出して各位置に1ずつ足しておかないとダメ(あるいは1, 2, 3, ...と初期化する)。
  • 1, 2, ...の位置を毎回愚直に探していると結局O(N2)になってしまうので、先にmap等に入れておく。
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;

class Bit {
private:
    vector<int> bit;
    int n;

public:
    Bit(int _n) {
        n = _n;
        bit.clear();
        bit.resize(n + 1, 0);
    }

    // get sum in [1, i]
    // sum{[i, j]} = sum{[1, j]} - sum{[1, i-1]}
    int sum(int i) {
        int s = 0;
        while (i > 0) {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    // add x to bit[i]
    void add(int i, int x) {
        while (i <= n) {
            bit[i] += x;
            i += i & -i;
        }
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int N;
    cin >> N;
    vector<int> a(N);
    map<int, int> pos;  // {a[i], i}
    rep(i, N) {
        cin >> a[i];
        pos[a[i]] = i + 1;
    }

    Bit bit(N); // 位置i(1-index)にブロックがある -> 1, else -> 0
    rep(i, N) bit.add(i + 1, 1);    // 最初、各位置にブロックがある
    int ans = 0;
    for (auto p : pos) {
        int i = p.second;
        // このブロックはmin(左にあるブロックの個数, 右にあるブロックの個数) だけ動かす
        ans += min(bit.sum(i - 1), bit.sum(i + 1, N));
        // このブロックを消す
        bit.add(i, -1);
    }

    cout << ans << endl;

}

問題が解けないときは本質をわかっていないことが多い。