yukicoder No.1827 最長部分スーパーリッチ門松列列

問題

yukicoder.me

解法

$\displaystyle v = \min _ { i : \mathrm{even} } a _ i \gt \max _ { i : \mathrm{odd} } a _ i$ または $\displaystyle v = \min _ { i : \mathrm{odd} } a _ i \gt \max _ { i : \mathrm{even} } a _ i$ を満たす $v = p _ k$ を固定した場合の長さの最大値を考える。

列 $x = (x _ 1, \ldots, x _ N)$ および $y = (y _ 1, \ldots, y _ {N - 1})$ を以下で定義する。 $$ \begin{aligned} x _ i & := \begin{cases} -1 & \text{if $p _ i = v\;(\mathrm{i.e.}\; i = k)$} \\ 0 & \text{if $p _ i \lt v$} \\ +1 & \text{if $p _ i \gt v$} \end{cases} , \\ y _ i & := \begin{cases} 1 & \text{if $x _ i \neq x _ { i + 1 }$} \\ 0 & \text{if $x _ i = x _ { i + 1 }$} \end{cases} . \end{aligned} $$

$x$ において同じ値が連続する部分を $1$ つのブロックとして見ることにすると、例えば $x,y$ は下図のようになる。

$\displaystyle p _ k = \min _ { i : \mathrm{even} } a _ i \gt \max _ { i : \mathrm{odd} } a _ i$ または $\displaystyle p _ k = \min _ { i : \mathrm{odd} } a _ i \gt \max _ { i : \mathrm{even} } a _ i$ を満たす最長の門松列列を得るためには、$i\gt k$ の部分に関しては $x$ の値が $0,1,0,1,\ldots$ となるように添字の小さい方から貪欲に選ぶのが最適であり、$i\lt k$ の部分に関しては $x$ の値が $\ldots,1,0,1,0$ となるように添字の大きい方から貪欲に選ぶのが最適である。つまり、最長の門松列列の長さは $(\text{ブロックの個数}) - (\text{$-1$ ブロックに隣接する $1$ ブロックの個数})$ として求めることが出来る。

$-1$ ブロックに隣接する $1$ ブロックの個数に関しては、$x _ i = -1$ となるのは $i = k$ に限られるので $x _ {k - 1} = 1$ と $x _ {k + 1} = 1$ をチェックすればよく、$O(1)$ で計算できる。 一方、$p_k$ の昇順に見るなど、適切な順序で見れば $x$ 自体の更新箇所は毎回 $O(1)$ 個で済むが、要素の更新に対してブロック数を管理するのはやや面倒である ¹。

ここで、ブロックの個数は $y_i=1$ を満たす $i$ の個数に $1$ を加えたものに一致することに注目する。$x$ の更新に対して $y$ を更新するのは容易であるから、$x$ のブロック数の代わりに $y$ と $y_i=1$ を満たす $i$ の個数を管理することにすれば、これは $O(1)$ で更新可能である。

以上より、各テストケースを $ \Theta(N)$ で解くことが出来た。

実装

提出 (C++17 (gcc 11.2.0 + boost 1.78.0), 56 ms, AC)

#include <iostream>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t --> 0) {
        int n;
        std::cin >> n;
        std::vector<int> p(n);
        for (auto &e : p) {
            std::cin >> e;
            --e;
        }
        std::vector<int> q(n);
        for (int i = 0; i < n; ++i) {
            q[p[i]] = i;
        }
        int block_num = 1;
        std::vector<int> x(n, 1);
        auto update = [&](int i, int v) {
            block_num -= i > 0     and x[i - 1] != x[i];
            block_num -= i + 1 < n and x[i + 1] != x[i];
            x[i] = v;
            block_num += i > 0     and x[i - 1] != x[i];
            block_num += i + 1 < n and x[i + 1] != x[i];
        };

        int ans = 0;
        for (int i : q) {
            update(i, -1);
            int len = block_num;
            len -= i > 0     and x[i - 1] == 1;
            len -= i + 1 < n and x[i + 1] == 1;
            ans = std::max(ans, len);
            update(i, 0);
        }
        std::cout << ans << '\n';
    }
    return 0;
}

---

1. いわゆる「区間を管理する set」を用いれば $O(\log N)$ time で更新可能であるが、ここでは割愛する。区間を管理する set に関しては 区間をsetで管理するやつでもうバグらせたくない - むげんのぶろぐ などを参照。↩