概要

カード列をいくつかの単調非増加な山に分ける問題です。
山の数を最小にしつつ、さらに \(B_1+B_2+\cdots+B_N\) が最大になる積み方を求めます。

考察

カードを左から右に処理すると、「どの山に置くか」は典型的な貪欲法で山数を最小化できます。
しかし、それだけでは \(B_i\) の総和が最大になるとは限りません。

そこで、右から左に処理することを考えます。

元のルールでは、カード \(i\) の上にカード \(j\) を置ける条件は

\[ i < j,\quad A_i \geq A_j \]

です。

これを右から左に見ると、すでに作っている山の「現在の一番下のカード」の値を \(x\)、これから下に追加したいカードの値を \(y\) として、

\[ x \leq y \]

なら、その山の下にカードを追加できます。

つまり右から左に処理すると、

• 既存の山の一番下の値が \(A_i\) 以下なら、カード \(i\) をその下に置ける
• 置ける山がなければ、新しい山を作る

という問題になります。

ここで、置ける山が複数ある場合は、一番下の値が \(A_i\) 以下のもののうち、最大の値を持つ山を選びます。

これは典型的な貪欲法です。
より大きい値を持つ山を使っておくことで、小さい値を持つ山を残せます。小さい値の山は、今後さらに左側のカードを置ける可能性が高いためです。

例えば、現在の山の一番下の値が

\[ 1,\ 5 \]

で、今見ているカードの値が \(6\) だとします。

• 値 \(1\) の山に置くと、残る一番下の値は \(5,\ 6\)
• 値 \(5\) の山に置くと、残る一番下の値は \(1,\ 6\)

後者の方が、値 \(1\) の山を残せるので今後有利です。

---

次に、なぜ \(B_i\) の総和最大化にも対応できるかを考えます。

ある山において、カードが

\[ c_1, c_2, \ldots, c_m \]

の順に下から上へ積まれているとします。

このとき、

\[ B_{c_1}=0,\quad B_{c_2}=c_1,\quad B_{c_3}=c_2,\quad \ldots \]

です。

つまり、\(B\) の総和には「上にカードが存在するカード」の番号がちょうど 1 回ずつ足されます。
言い換えると、

\[ B_1+B_2+\cdots+B_N = 1+2+\cdots+N - \text{各山の一番上のカード番号の総和} \]

です。

山の数 \(K\) が固定なら、\(B\) の総和を最大化することは、各山の一番上のカード番号の総和を最小化することと同じです。

右から左に処理すると、新しい山を作った瞬間のカードが、その山の「一番上のカード」になります。

したがって、右から左への貪欲法で

• 置けるなら既存の山の下に置く
• 置けないときだけ新しい山を作る

とすると、新しい山を作る位置をできるだけ左側、つまりカード番号が小さい位置にできます。

その結果、各山の一番上のカード番号の総和が最小になり、\(B_1+B_2+\cdots+B_N\) が最大になります。

アルゴリズム

右から左へカードを見ます。

各山について、現在分かっている「一番下のカード」を管理します。
カード \(i\) を処理するとき、値を \(A_i\) とします。

操作

1. 現在存在する山のうち、一番下のカードの値が \(A_i\) 以下のものを探す
2. その中で、一番下の値が最大の山を選ぶ
3. そのような山が存在する場合
   • その山の現在の一番下のカードを \(j\) とする
   • カード \(i\) をカード \(j\) の直下に置く
   • よって \(B_j=i\)
   • 山の一番下のカードを \(i\) に更新する
4. 存在しない場合
   • 新しい山を作る
   • 山数 \(K\) を \(1\) 増やす

データ構造

\(A_i\) は最大 \(10^9\) なので、座標圧縮します。

そのうえで、以下を管理します。

• stacks[r]
  • 値の圧縮後の順位が \(r\) である「現在の山の一番下のカード番号」のリスト
• Fenwick Tree
  • 各順位 \(r\) に、現在その値を一番下に持つ山が何個あるかを管理

カード \(i\) の圧縮後の値を \(r\) とします。

Fenwick Tree で

\[ \text{順位 } 1 \text{ から } r \text{ までの山の個数} \]

を求めます。

これが \(0\) なら、置ける山はありません。

\(0\) でないなら、順位 \(r\) 以下で存在する最大の順位 \(p\) を Fenwick Tree 上で二分探索します。
その順位 \(p\) の山を 1 つ取り出し、カード \(i\) をその下に置きます。

計算量

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

座標圧縮に \(O(N \log N)\)、各カードの処理に Fenwick Tree の操作を行うため \(O(\log N)\) かかります。

実装のポイント

Fenwick Tree では、各値に対して現在の「山の一番下」の個数を管理します。

s = prefix_sum(r)

で、値が \(A_i\) 以下の山が存在するかを調べます。

存在する場合、s は「順位 \(r\) 以下にある山の個数」です。
Fenwick Tree 上で「累積和が s 以上になる最小の位置」を探すと、それが順位 \(r\) 以下で存在する最大の順位になります。

また、カード \(i\) を既存の山の下に置くとき、元々その山の一番下だったカードを \(j\) とすると、

b[j] = i

とします。

これは「カード \(j\) の直下にカード \(i\) がある」という意味です。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:]

    vals = sorted(set(a))
    comp = {v: i + 1 for i, v in enumerate(vals)}
    ranks = [comp[x] for x in a]
    m = len(vals)

    bit = [0] * (m + 1)
    stacks = [[] for _ in range(m + 1)]
    b = [0] * (n + 1)

    def add(i, v):
        while i <= m:
            bit[i] += v
            i += i & -i

    top_bit = 1 << (m.bit_length() - 1)

    k = 0

    for pos in range(n - 1, -1, -1):
        idx_card = pos + 1
        r = ranks[pos]

        s = 0
        x = r
        while x > 0:
            s += bit[x]
            x -= x & -x

        if s == 0:
            k += 1
            stacks[r].append(idx_card)
            add(r, 1)
        else:
            idx = 0
            need = s
            step = top_bit
            while step:
                nxt = idx + step
                if nxt <= m and bit[nxt] < need:
                    idx = nxt
                    need -= bit[nxt]
                step >>= 1

            p = idx + 1
            below = stacks[p].pop()
            b[below] = idx_card
            stacks[r].append(idx_card)

            if p != r:
                add(p, -1)
                add(r, 1)

    sys.stdout.write(str(k) + "\n" + " ".join(map(str, b[1:])) + "\n")

if __name__ == "__main__":
    main()

---

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