概要

この問題は、与えられたカードの列をルールに従って重ねていき、最終的な「山の数」を最小化しつつ、重ねた関係を表すインデックスの総和 \(\sum B_i\) を最大化する問題です。

カードを重ねる関係を「マッチング」として捉え、貪欲法（Greedy）と二分探索（std::set）を組み合わせることで、 \(O(N \log N)\) で効率的に解くことができます。

考察

問題の言い換え（マッチング）

カード \(i\) をカード \(j\) の上に重ねるための条件は以下の通りです： 1. \(j < i\) （カード \(j\) が先に置かれている） 2. \(A_j \geq A_i\) （下のカードの数値が上のカードの数値以上）

カード \(i\) の直下にカード \(j\) を置くことを、有向辺 \(j \to i\) と表すことにします。 各カードは「他のカードの下に敷かれる（親になる）」のも「他のカードの上に重ねられる（子になる）」のも、それぞれ高々1回ずつです。

このとき、重ねられたカードの総数（マッチング数）を \(M\) とすると、最終的な山の数は \(N - M\) となります。 したがって、山の数を最小化することは、マッチング数 \(M\) を最大化することと同値です。

さらに、直下のカードのインデックスの総和 \(\sum B_i\) を最大化したいという要求があります。これは、マッチングに選ばれる親のインデックス \(j\) の総和を最大化することと同じです。

貪欲法の設計

山の数を最小化（\(M\) を最大化）しつつ、親のインデックス \(j\) の総和を最大化するために、インデックスの大きい（右側にある）カード \(j\) から順に、マッチングの「親」として使えるかを決定していく貪欲法を考えます。

\(j\) を \(N\) から \(1\) まで逆順に見ていきます。 \(j\) を固定したとき、上に重ねられる候補（子）となるのは、 \(j < i\) を満たす未割り当てのカード \(i\) です。 この候補の中で、 \(A_i \leq A_j\) を満たすもののうち、どの \(i\) を選ぶべきでしょうか？

ここで、「\(A_i \leq A_j\) を満たすもののうち、 \(A_i\) が最大であるものを選ぶ」のが最適になります。 理由は以下の通りです： - \(A_i\) が小さいカードは、今後探索するより小さい \(j' (< j)\) に対してもマッチングできる可能性（許容範囲）が広いため、温存しておきたいです。 - したがって、今ある \(A_j\) でマッチングできる限界ギリギリの、できるだけ大きい \(A_i\) をここで消費してしまうのが、将来のマッチングの可能性を最も残す（狭めずに済む）賢い選択になります。

また、 \(j\) を大きい方（\(N\) から \(1\)）から順に走査し、マッチング可能なら即座にマッチングを成立させることで、大きなインデックス \(j\) が優先的に \(B_i\) の値として採用されるため、 \(\sum B_i\) も自動的に最大化されます。

アルゴリズム

具体的には、以下の手順で処理を行います。

1. データ構造の準備:

   • まだマッチングの「子」として使われていないカードの集合 s を用意します。これは値 \(A_i\) とインデックス \(i\) のペア (A[i], i) を管理する平衡二分探索木（C++ の std::set）とします。
   • B 配列を \(0\) で初期化します。

2. 逆順ループ:

   • \(j\) を \(N\) から \(1\) までデクリメントしながらループを回します。
   • ループの各ステップ \(j\) において：
     1. \(j < N\) であれば、カード \(j+1\) が「子」の候補として利用可能になるため、 s に (A[j+1], j+1) を挿入します。
     2. s の中から、 \(A_i \leq A_j\) を満たす最大の \(A_i\) を持つ要素を二分探索（upper_bound）で探します。
     3. 条件を満たす要素 \(i\) が見つかった場合：
        • \(B_i = j\) とします。
        • その要素 \(i\) を s から削除します（1つのカードは1度しか重ねられないため）。
        • マッチング数 \(M\) を 1 増やします。

3. 出力:

   • 最小の山の数 \(K = N - M\) を出力します。
   • 配列 \(B_1, \ldots, B_N\) を出力します。

具体例でのシミュレーション

\(N = 4\), \(A = [4, 2, 3, 1]\) の場合を考えます。

• \(j = 4\) (\(A_4 = 1\)):
  • s は空。マッチングなし。
• \(j = 3\) (\(A_3 = 3\)):
  • s に (A_4, 4) = (1, 4) を追加。 s = {(1, 4)}。
  • \(A_i \leq A_3 (3)\) を満たす最大は \(A_4 = 1\)。
  • \(B_4 = 3\) とし、 s から削除。 s = {}, \(M = 1\)。
• \(j = 2\) (\(A_2 = 2\)):
  • s に (A_3, 3) = (3, 3) を追加。 s = {(3, 3)}。
  • \(A_i \leq A_2 (2)\) を満たすものは s に存在しない（\(3 > 2\) のため）。マッチングなし。
• \(j = 1\) (\(A_1 = 4\)):
  • s に (A_2, 2) = (2, 2) を追加。 s = {(2, 2), (3, 3)}。
  • \(A_i \leq A_1 (4)\) を満たす最大は \(A_3 = 3\)。
  • \(B_3 = 1\) とし、 s から削除。 s = {(2, 2)}, \(M = 2\)。

結果: - 山の数 \(K = 4 - 2 = 2\) - \(B = [0, 0, 1, 3]\) （これは、山1: \(1 \to 3 \to 4\)、山2: \(2\) となり、確かに条件を満たします）

計算量

• 時間計算量: \(O(N \log N)\)
  • \(j\) のループは \(N\) 回回ります。
  • 各ループ内での std::set への挿入（insert）、二分探索（upper_bound）、削除（erase）はすべて \(O(\log N)\) で行えます。
  • したがって、全体の時間計算量は \(O(N \log N)\) となり、 \(N \leq 2 \times 10^5\) の制約下で実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N)\)
  • 配列 \(A, B\) および std::set のサイズは最大でも \(N\) であるため、空間計算量は \(O(N)\) です。

実装のポイント

• std::set での二分探索:

  • A[i] <= A[j] を満たす最大の要素を探すために、 s.upper_bound({A[j], N + 1}) を使用しています。
  • upper_bound は指定した値より「厳密に大きい」最初の要素を指すイテレータを返します。そのため、得られたイテレータを1つ手前に戻す（--it）ことで、 A[i] <= A[j] を満たす最大の要素を指すことができます。
  • イテレータが s.begin() を指している場合は、条件を満たす要素が存在しないことを意味するため、安全にスキップする必要があります。

• ペアの比較順序:

  • std::set<pair<int, int>> は、第一要素（カードに書かれた数値 \(A_i\)）でまず比較され、同じ場合は第二要素（インデックス \(i\)）で比較されます。これにより、数値の大小を基準とした二分探索が正しく行われます。

    ソースコード

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

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

    vector<int> B(N + 1, 0);
    // 利用可能なカード i を {A[i], i} のペアで管理する
    set<pair<int, int>> s;
    int M = 0; // マッチング数（重ねられたカードの数）

    // 右側のカードから順にマッチングの親（下になるカード）として選べるか走査する
    for (int j = N; j >= 1; --j) {
        // j より右側にあるカード j + 1 が新たに利用可能になる
        if (j < N) {
            s.insert({A[j + 1], j + 1});
        }
        
        // A[i] <= A[j] を満たす最大の A[i] を持つ要素を二分探索
        auto it = s.upper_bound({A[j], N + 1});
        if (it != s.begin()) {
            --it; // 条件を満たす最大の要素を指すようにデクリメント
            int i = it->second;
            B[i] = j;      // カード i の直下のカードを j に設定
            s.erase(it);   // 使用したカードを候補から削除
            M++;
        }
    }

    // 山の数の最小値 K = N - (重ねられたカードの数)
    cout << N - M << "\n";
    for (int i = 1; i <= N; ++i) {
        cout << B[i] << (i == N ? "" : " ");
    }
    cout << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。