頑張った

問題へのリンク

問題概要

正の整数のみからなる長さ $N$ の数列 $A_{1}, \dots, A_{N}$ が与えられる。各 $k = 1, 2, \dots, N$ に対して、以下の問に答えよ。

数列 $A$ を左から順に「連続する $k$ 個の最小値」をとっていってできる長さ $N - k + 1$ の数列が、 $1, 2, \dots, N -k+1$ の順列になっているかどうかを判定せよ。

制約

$N$ の総和 $\le 3 \times 10^{5}$

考えたこと

$k = 1$ の場合は自明に判定できるので別途処理しておく。

まず、数列中に 1 が存在しない場合はすべての $k$ で No となる。数列中に 1 が存在するときも、

1 が左端のみにある
1 が右端のみにある

といういずれかの条件を満たさない場合、 $k = 1, N$ を除いて No となる。たとえば $A = (4, 1, 2, 3, 5, 6, 3)$ などの場合、 $k = 1, N$ の場合以外では 2 回以上 1 が登場してしまうのだ。

1 が左端にあるとしよう (右端の場合も同様)。このとき、その「左端の 1」を除いた長さ $N-1$ の数列について、同様のプロセスで考えることができる。つまり、

2 が左端のみにある (そして 1 が存在しない)
2 が右端のみにある (そして 1 が存在しない)

といういずれかの条件を満たさない場合、 $k = 2, 3, \dots, N-2$ はすべて No となる。

以下同様に、これを繰り返して区間長が $N - x$ の状態になったとき、

$x+1$ が左端のみにある (そして $x$ 以下の値が存在しない)
$x+1$ が右端のみにある (そして $x$ 以下の値が存在しない)

といういずれかの条件を満たさない場合、 $k = 2, 3, \dots, N-x-1$ はすべて No となる。

逆に、区間長が $N-x$ の状態で初めて上述の "両端条件" を満たさなくなったとき、 $k = N-x, N-x+1, \dots, N$ では条件を満たすことも言える。

コード

区間の長さが 1 ずつ減っていく。それぞれの場合について区間の最小値を取る作業を RMQ を使って実施した。この実装の場合、計算量は $O(N\log N)$ となる。

#include <bits/stdc++.h>
using namespace std;

template<class Monoid> struct RMQ {
    Monoid INF;
    int SIZE_R;
    vector<pair<Monoid,int> > dat;
    
    RMQ() {}
    RMQ(int n, const Monoid &inf): INF(inf) { 
        init(n, inf);
    }
    void init(int n, const Monoid &inf) {
        INF = inf;
        SIZE_R = 1;
        while (SIZE_R < n) SIZE_R *= 2;
        dat.assign(SIZE_R * 2, pair<Monoid,int>(INF, -1));
    }
    
    /* set, a is 0-indexed */
    void set(int a, const Monoid &v) { dat[a + SIZE_R] = make_pair(v, a); }
    void build() {
        for (int k = SIZE_R - 1; k > 0; --k) {
            dat[k] = min(dat[k*2], dat[k*2+1]);
        }
    }
    
    /* update, a is 0-indexed */
    void update(int a, const Monoid &v) {
        int k = a + SIZE_R;
        dat[k] = make_pair(v, a);
        while (k >>= 1) dat[k] = min(dat[k*2], dat[k*2+1]);
    }
    
    /* get {min-value, min-index}, a and b are 0-indexed */
    pair<Monoid,int> get(int a, int b) {
        pair<Monoid,int> vleft = make_pair(INF, -1), vright = make_pair(INF, -1);
        for (int left = a + SIZE_R, right = b + SIZE_R; left < right; left >>= 1, right >>= 1) {
            if (left & 1) vleft = min(vleft, dat[left++]);
            if (right & 1) vright = min(dat[--right], vright);
        }
        return min(vleft, vright);
    }
    inline Monoid operator [] (int a) { return dat[a + SIZE_R].first; }
    
    /* debug */
    void print() {
        for (int i = 0; i < SIZE_R; ++i) {
            Monoid val = (*this)[i];
            if (val < INF) cout << val;
            else cout << "INF";
            if (i != SIZE_R-1) cout << ",";
        }
        cout << endl;
    }
};

const int INF = 1<<29;
int N;
vector<int> A;
RMQ<int> rmq;

void solve(int left, int right, int val, vector<int> &res) {
    if (left >= right) return;
    auto mi = rmq.get(left, right);
    int vmin = mi.first, pmin = mi.second;

    //cout << "------------" << endl;
    //COUT(left); COUT(vmin); COUT(val); COUT(right); COUT(mi);

    if (vmin != val) {
        for (int i = right - left; i > 1; --i) res[i-1] = 0;
        return;
    }
    if (pmin == left) solve(left + 1, right, val + 1, res);
    else if (pmin == right - 1) solve(left, right - 1, val + 1, res);
    else for (int i = right - left - 1; i > 1; --i) res[i-1] = 0;
}

int main() {
    int TTT; cin >> TTT;
    while (TTT--) {
        cin >> N;
        A.resize(N);
        rmq.init(N+10, 1<<29);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
            --A[i];
            rmq.set(i, A[i]);
        }
        rmq.build();
        
        auto B = A;
        sort(B.begin(), B.end());
        bool ok = true;
        for (int i =0 ; i < N; ++i) if (B[i] != i) ok = false;
        vector<int> res(N, 1);
        if (!ok) res[0] = 0;
        solve(0, N, 0, res);
        for (int i = 0; i < res.size(); ++i) cout << res[i];
        cout << endl;
    }
}

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

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

Codeforces Global Round 12 D. Rating Compression (R1800)

問題概要

制約

考えたこと

コード