シミュレーションと呼ばれるジャンルの中では、最も重たい部類の問題

問題へのリンク

問題概要

1 から $N$ までの整数の書かれたカードがこの順に並んでいる。このカード列に以下の $M$ 回の操作を行う。

$i$ 回目の操作は、整数 $x_{i}, y_{i}$ （ $1 \le x_{i} \lt y_{i} \lt N$ ）によって表される。操作前のカードの山に対して、

$y_{i}+1$ 枚目から $N$ 枚目まで
$x_{i}+1$ 枚目から $y_{i}$ 枚目まで
$1$ 枚目から $x_{i}$ 枚目まで

をこの順に並べ替える。

このような操作を行なった後のカードの山について、 $p$ 枚目から $q$ 枚目までの間に、 $r$ 以下の整数値のカードが何枚あるかを求めよ。

制約

$1 \le N \le 10^{9}$
$1 \le M \le 5000$

考えたこと

カードの山について、「整数が連続している箇所」については圧縮して表現することにしょう。初期状態のカードの山は $\lbrack 1, N+1)$ と表せる。

たとえば、 $N = 9$ に対して、 $x = 3, y = 5$ による操作を行うとカードの山は $6,7,8,9,4,5,1,2,3$ となる。これは

$\lbrack 6, 10), \lbrack 4, 6), \lbrack 1, 4)$

というように表現できる。

さて、ここで注目したいことは、 $N$ が大きくて $M$ が小さいことだ。1 回の操作によって、上記表現における区間の個数は高々 2 個しか増えないので、 $M$ 回操作後のカードの山を表す区間の個数も $O(M)$ でおさえられる。

よって、 $M$ 回の操作を愚直に実装すると $O(M^{2})$ の計算量で実装できる。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;

// 「区間の集まり」に対して、区間 [x, y) で切ってできる「区間の集まり」
vector<pint> divide(const vector<pint> &v, int x, int y) {
    vector<pint> res;
    int sum = 0, left, right;
    for (int i = 0; i < v.size(); i++) {
        int len = v[i].second - v[i].first;
        if (sum + len <= x || sum >= y) {
            sum += len;
            continue;
        }
        if (sum <= x) left = v[i].first + (x - sum);
        else left = v[i].first;
        if (y <= sum + len) right = v[i].first + (y - sum);
        else right = v[i].second;
        res.emplace_back(left, right);
        sum += len;
    }
    return res;
};

int main() {
    int N, M, p, q, r, x, y;
    cin >> N >> M >> p >> q >> r;
    --p;
    vector<pint> v({pint(1, N + 1)});
    for (int i = 0; i < M; i++) {
        vector<pint> v2;
        cin >> x >> y;
        auto div1 = divide(v, 0, x), div2 = divide(v, x, y), div3 = divide(v, y, N);
        for (auto p : div3) v2.push_back(p);
        for (auto p : div2) v2.push_back(p);
        for (auto p : div1) v2.push_back(p);
        swap(v, v2);
    }

    // [p, q) を取り出す
    v = divide(v, p, q);
    int res = 0;
    for (auto [left, right] : v) {
        right = min(right, r+1);
        if (left < right) res += right - left;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 予選 2009 E - シャッフル (AOJ 0536) (2D, 難易度 8)

問題概要

制約

考えたこと

コード