概要

カードを左から順に「値が単調非増加」になるように山へ積む問題です。
逆向きに見ると「値が単調非減少」になる列へ分ける問題になり、貪欲法と set で最小の山数と最適な \(B_i\) を求めます。

考察

元の山を下から上へ見ると、カード番号は増加し、値は単調非増加です。

例えば、ある山が

\[{p_1 < p_2 < \cdots < p_m}\]

の順に積まれているなら、

\[A_{p_1} \geq A_{p_2} \geq \cdots \geq A_{p_m}\]

です。

これを右から左、つまりカード \(N, N-1, \ldots, 1\) の順に見ると、同じ山は

\[p_m, p_{m-1}, \ldots, p_1\]

の順に現れ、値は

\[A_{p_m} \leq A_{p_{m-1}} \leq \cdots \leq A_{p_1}\]

となります。

つまり、問題は逆から見ると「列をできるだけ少ない個数の単調非減少列に分ける問題」と考えられます。

---

逆向きに処理しているとき、ある部分的な山の「現在の一番下のカード」を管理します。

カード \(i\) をその山の下に追加できる条件は、現在の一番下のカードを \(j\) として、

\[A_i \geq A_j\]

です。

このとき、元の向きではカード \(j\) の直下にカード \(i\) があるので、

\[B_j = i\]

となります。

---

最小の山数を得るためには、現在のカード \(i\) を置ける山があるなら、その中で「現在の一番下の値」が最大の山に置くのが最適です。

理由は、小さい値で終わっている山ほど、今後さらに小さいカードを受け止められる可能性が高いためです。
置ける山の中で最大の値を持つ山を使うことで、小さい値の山を温存できます。

これは、列を最小個数の単調非減少列に分けるときの標準的な貪欲法です。

例えば、逆順で見た値が

\[2, 1, 2, 1\]

だったとします。

途中で山の末尾の値が \(1, 2\) になっている状態で、次に \(2\) を処理する場合、

• 値 \(2\) の山に置くと、末尾は \(1, 2\) のまま
• 値 \(1\) の山に置くと、末尾は \(2, 2\) になる

後者では次の \(1\) を置けなくなり、山が余分に増える可能性があります。

---

また、\(B_1 + B_2 + \cdots + B_N\) を最大化する条件も、この逆向き貪欲で満たされます。

逆向き処理でカード \(i\) を既存の山に追加すると、あるカードの \(B\) が \(i\) になり、和がちょうど \(i\) 増えます。

つまり、なるべく大きい番号のカードで「既存の山に追加する」ことが有利です。

この貪欲法は、各 suffix、つまりカード \(t, t+1, \ldots, N\) だけを見た場合にも、常に最小の山数を達成します。
したがって、その範囲内で作れる連結、すなわち \(B\) に貢献する回数も最大です。

任意の集合 \(S\) について、

\[\sum_{i \in S} i = \sum_{t=1}^{N} |\{i \in S \mid i \geq t\}|\]

が成り立ちます。
各 suffix で貢献回数が最大なので、結果として \(B_i\) の総和も最大になります。

アルゴリズム

set<pair<long long, int>> bottoms を用意します。

これは、各部分的な山について、

\[(現在の一番下のカードの値, そのカード番号)\]

を管理する集合です。

処理はカード \(N\) から \(1\) へ逆向きに行います。

カード \(i\) について、以下を行います。

1. bottoms の中から、値が \(A_i\) 以下であるものを探す
2. その中で値が最大のものを選ぶ
3. 見つからなければ、新しい山を作る
4. 見つかれば、そのカードを child として、 $\(B_{\text{child}} = i\)$ とする
5. その山の一番下はカード \(i\) に変わるので、集合を更新する

コードでは、

auto it = bottoms.upper_bound({A[i], numeric_limits<int>::max()});

によって、値が \(A_i\) 以下の要素の直後を探しています。

その直前の要素が「値が \(A_i\) 以下で最大」の候補になります。

計算量

• 時間計算量: \(O(N \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

A_i には同じ値が複数存在する可能性があります。
そのため、set には値だけでなくカード番号も含めた

pair<long long, int>

を入れています。

また、条件は \(A_j \leq A_i\) なので、等しい値も選べる必要があります。
そのため、

upper_bound({A[i], INF})

として、値が \(A_i\) 以下の要素をすべて候補に含めています。

ソースコード

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

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

    int N;
    cin >> N;

    vector<long long> A(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];

    vector<int> B(N + 1, 0);
    set<pair<long long, int>> bottoms;

    int K = 0;

    for (int i = N; i >= 1; i--) {
        auto it = bottoms.upper_bound({A[i], numeric_limits<int>::max()});

        if (it == bottoms.begin()) {
            bottoms.insert({A[i], i});
            K++;
        } else {
            --it;
            int child = it->second;
            B[child] = i;
            bottoms.erase(it);
            bottoms.insert({A[i], i});
        }
    }

    cout << K << '\n';
    for (int i = 1; i <= N; i++) {
        if (i > 1) cout << ' ';
        cout << B[i];
    }
    cout << '\n';

    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。