解説

何か全探索できそうな部分は無いだろうか。
もう少し具体的に言うと、固定してしまうと嬉しいような部分が無いだろうか。

中心を固定する

B[X+1]が固定されていたとする。
すると、左右は単調減少列と単調増加列となり、レベルが最も高いようにしたいのであれば、左右の増加列の最長である方が嬉しい。
よって、中心を固定することにより、単調減少列・単調増加列の最長を求める問題となった。
これは、LISと言って典型問題となる。

実装のために

実装のために、B1＜B2＜B3＜…＜BX+1＜BX+2＜…＜B2X+1の場合のみ考えよう。
もう片方を考えたいときは、A[i]を-A[i]のように変換して同じアルゴリズムを使えば実質的にもう片方の条件で確認することができる。

LIS

最長増加列の略であるが、色々なやり方がある。
左右からLISを見ていき、以下の配列を作成していく。

lft[i] := 先頭から作るときのA[i]で終わる最長単調増加列
rht[i] := 末尾から作るときのA[i]で始まる最長単調減少列

これを先に作ってしまえば、中心を固定したときの最大レベルはmin(lft[i], rht[i]) - 1となる。
これの最大値が答え。

int N, _A[101010], A[101010];
//---------------------------------------------------------------------------------------------------
SegTree<int, 1<<17> st;
int lft[101010], rht[101010];
int solve() {
    compress1(A, N);

    rep(i, 0, N) lft[i] = rht[i] = 0;

    rep(i, 0, N) st.update(i, 0);
    rep(i, 0, N) {
        chmax(lft[i], st.get(0, A[i]) + 1);
        st.update(A[i], max(st[A[i]], lft[i]));
    }

    rep(i, 0, N) st.update(i, 0);
    rrep(i, N - 1, 0) {
        chmax(rht[i], st.get(0, A[i]) + 1);
        st.update(A[i], max(st[A[i]], rht[i]));
    }

    int ans = 0;
    rep(i, 0, N) chmax(ans, min(lft[i], rht[i]) - 1);
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> _A[i];

    int ans = 0;

    rep(i, 0, N) A[i] = _A[i];
    chmax(ans, solve());

    rep(i, 0, N) A[i] = -_A[i];
    chmax(ans, solve());

    cout << ans << endl;
}

はまやんはまやんはまやん

hamayanhamayan's blog

レベルX門松列 [yukicoder 1188]

解説

中心を固定する

実装のために

LIS