Day 172-Q3 | k 本の増加部分列（Greene の定理と RSK）

問題

$1,\dots,N$ の順列 $P=(P_1,\dots,P_N)$ と整数 $K$ が与えられる。$k=1,2,\dots,K$ のそれぞれについて、次の値 $a_k$ を求めよ。

$P$ から互いに素な（同じ添字を共有しない） $k$ 本の増加部分列を選ぶ。選んだ部分列の長さの合計の最大値を $a_k$ とする（空の部分列も可）

$a_1,\dots,a_K$ を空白区切りで出力せよ。

入力形式

N K
P_1 P_2 ... P_N

制約

#	条件
1	$1\le N\le 2\times10^5$
2	$1\le K\le 50$
3	$P$ は $1,\dots,N$ の順列

入出力例

入力例1

6 2
2 3 6 1 4 5

出力例1

4 6

（LIS は 2 3 4 5 の 1 本だけで長さ 4。これを取ると残りは 6 1 で、増加部分列は長さ 1。合計 5。だが 2 3 6 と 1 4 5 を選べば 6。どの LIS を取り除いても最適にならない最小の例（$N\le5$ の全順列には無いことを全探索で確認））

入力例2

7 3
7 6 5 4 3 2 1

出力例2

1 2 3

入力例3

6 3
3 1 4 5 2 6

出力例3

4 6 6

（3 例とも、各要素を「どの部分列に入れるか／入れないか」の全列挙と一致）

背景と出典

Schensted の定理（1961）: 順列を RSK（Robinson–Schensted–Knuth）の挿入で表に入れると、表の 1 行目の長さが LIS の長さ、1 列目の長さが最長減少部分列の長さになる

Greene の定理（1974）: もっと強く、表の形 $\lambda=(\lambda_1\ge\lambda_2\ge\cdots)$ について、$\lambda_1+\cdots+\lambda_k$ が「互いに素な $k$ 本の増加部分列の合計長の最大」に等しい（減少部分列は列の長さで同様）

いずれも私の記憶による（C. Greene, "An extension of Schensted's theorem", Advances in Mathematics, 1974 と記憶。本セッションでは原典を参照していない）。本問の答えが $\lambda$ の部分和になることは、最小費用流（各要素を容量 1 の頂点にした $k$ 本の流れ）と全列挙で確かめた。

本問は自作。$K$ が小さいとき、表の上 $K$ 行だけを持てばよいことが計算量の要点になる。

概念図

ヒント（クリックで段階的に開示）

ヒント1（方向性）

LIS を 1 本取り除いて、残りの LIS を足す貪欲を、入力例 1 で試す。なぜ失敗するのかを見ると、「2 本を同時に決める」必要があるとわかる。最小費用流（$k$ 単位の流れ）なら正しいが、$N=2\times10^5$ では重い。

ヒント2（アプローチ）

patience sorting（LIS を二分探索で求める方法）では、1 行の配列に「$x$ 以上の最小の要素を $x$ で置き換える」。置き換えられた要素を捨てずに 2 行目に同じ操作で挿入し、そこで押し出された要素を 3 行目へ……と続けるのが RSK の行挿入。各行の長さが答えの材料になる。

ヒント3（誘導）

$a_k=\lambda_1+\cdots+\lambda_k$（Greene の定理）。$K$ 行目から押し出された要素は $K+1$ 行目以降に入り、上 $K$ 行には二度と戻らない。だから上 $K$ 行だけ持ち、$K$ 行目から押し出された要素は捨ててよい。

for row in rows:                 # rows は K 本のソート済み配列
    i = bisect_left(row, x)
    if i == len(row): row.append(x); break
    row[i], x = x, row[i]        # 押し出された要素を次の行へ

模範解答 (Python)

模範解答を表示する（まず自力で解いてから）

import sys
from bisect import bisect_left


def main():
    data = sys.stdin.buffer.read().split()
    n, K = int(data[0]), int(data[1])
    p = data[2:2 + n]
    rows = [[] for _ in range(K)]          # RSK の挿入表の上 K 行だけを持つ
    for x in map(int, p):
        for row in rows:
            i = bisect_left(row, x)        # x 以上の最小の要素を押し出す（値は相異なる）
            if i == len(row):
                row.append(x)              # 押し出す要素が無ければ行末に置いて終わり
                break
            row[i], x = x, row[i]          # 押し出された要素が次の行へ挿入される
        # K 行目から押し出された要素は K+1 行目以降へ行くが、上 K 行には二度と戻らないので捨ててよい
    out = []
    s = 0
    for row in rows:
        s += len(row)
        out.append(s)                      # Greene の定理: k 本の増加部分列の和集合の最大 = λ1+…+λk
    print(*out)


main()

計算量: 1 要素の挿入で最大 $K$ 行を二分探索するので $O(NK\log N)$。$N=2\times10^5$、$K=50$ でランダム順列 1.74 s、減少列 0.78 s（Python 3.14.7、M1 MacBook Pro、実測）。全行を持つ版（$K$ を行数以上にした場合）はランダム順列で 10.08 s。

Step-by-Step 解説

1貪欲がなぜ誤るか

入力例 1 2 3 6 1 4 5 の LIS は 2 3 4 5 だけ。これを取ると 6 1 が残り、2 本目は長さ 1。合計 5。最適は 2 3 6＋1 4 5 の 6 で、1 本目を LIS より短くして 2 本目に 4 5 を譲っている。$k$ 本を同時に決めないと最適にならない。

2RSK の行挿入

表（各行が昇順の配列）に $x$ を入れる。1 行目で「$x$ 以上の最小の要素」を $x$ で置き換え、押し出された要素を 2 行目に同じように入れる。押し出すものが無ければ行末に置いて終わり。入力例 1 では

入れた値	1 行目	2 行目
2	2
3	2 3
6	2 3 6
1	1 3 6	2
4	1 3 4	2 6
5	1 3 4 5	2 6

形は $\lambda=(4,2)$。$a_1=4$、$a_2=6$。

3Greene の定理

$\lambda_1+\cdots+\lambda_k$ が「互いに素な $k$ 本の増加部分列の合計長の最大」。表の中身（どの値がどの行か）は部分列そのものではない（1 行目 1 3 4 5 は増加部分列ではない: 1 は 3 より後に出てくる）。形だけが答えを持っている。

4上 K 行だけ持つ

行 $r$ から押し出された要素は行 $r+1$ に入る。上の行に戻る操作は無いので、上 $K$ 行の内容は $K+1$ 行目以降に何が起きても変わらない。だから $K$ 行目から押し出された要素は捨ててよい。$N=2000$ 程度の 60 ケースで、全行を持つ版と上 $K$ 行版の出力が一致（実測）。

5計算量の差

ランダム順列の表は約 $2\sqrt N$ 行（$N=2\times10^5$ で 880 前後）。全行を持つと挿入 1 回で平均数十〜数百行を通り 10.08 s、上 50 行で打ち切ると 1.74 s、上 10 行なら 0.43 s（実測）。

迷った他案と採らなかった理由

案	計算量	採否	理由
要素ごとに「どの部分列に入れるか」の全列挙	$(k+1)^N$	検算用のみ	$N\le8$、$k\le3$ の 400 ケース
最小費用流（頂点を容量 1・費用 $-1$ に分割、流量 $k$）	Bellman–Ford で $O(k\cdot N^3)$ 程度	検算用のみ	$N\le40$ の 300 ケースで一致。$N=2\times10^5$ では辺が $O(N^2)$
LIS を 1 本ずつ取り除く貪欲	$O(KN\log N)$	不採用	誤り（入力例 1）
RSK の全行を持つ	$O(N\sqrt N\log N)$ 程度	不採用	10.08 s（実測）
RSK の上 $K$ 行だけ持つ（本解）	$O(NK\log N)$	採用	1.74 s 以下

前提が変わったら:

$K$ が $N$ 程度まで（すべての $k$ の答え）なら全行が要る。Python では $N=2\times10^5$ で 10 s 前後かかるので、C++ にするか、形だけを求める別の方法（本セッションでは調べていない）が要る
減少部分列なら、列の長さ（転置した形）の部分和。値を $N+1-P_i$ に反転して同じコードに入れればよい
部分列そのものを出力させるなら、形だけでは足りない。最小費用流で流れを復元するか、Greene の定理の構成的な証明に従う必要がある

よくあるミス

ミス	原因	正しい書き方
LIS を 1 本ずつ取り除く	1 本目を最長にするのが最適だと思う	全列挙 400 ケース中 4、流れとの照合 300 ケース中 74 で誤答（実測。取る LIS の選び方は二分探索で最後に見つかったもの）。入力例 1 はどの LIS を取っても誤る
表の 1 行目を「LIS そのもの」と思う	長さだけが LIS と一致する	入力例 1 の 1 行目 `1 3 4 5` は増加部分列ではない
`bisect_right` を使う	値が相異なる順列では同じだが、重複ありに広げると変わる	狭義増加なら `bisect_left`、広義増加なら `bisect_right`
$K$ 行目から押し出された要素を最終行に足す	「捨てると数が合わない」と思う	上 $K$ 行の長さの和だけが要る。押し出された要素は $K+1$ 行目以降の話

次のステップ

発展1: 重複ありの列で「広義増加」の $k$ 本（bisect_right 版）と、その全列挙での照合

発展2: $k$ 本の増加部分列を実際に構成して出力する（最小費用流の復元、$N\le2000$）
発展3: 原典（Schensted 1961、Greene 1974）で定理の主張と証明を確かめる（本セッションでは未確認）

検証ログ（本セッションで実行した数値）

全列挙との照合（実測）: $N\le8$、$K\le3$ のランダム順列 400 ケースで不一致 0

最小費用流との照合（実測）: $5\le N\le40$、$K\le6$ の 300 ケースで不一致 0
全行版との照合（実測）: $500\le N\le3000$、$K\le50$（一部はブロック状に並べ替えた順列）の 60 ケースで上 $K$ 行版と不一致 0
貪欲の誤答（実測）: 全列挙 400 ケース中 4、流れ 300 ケース中 74。「どの LIS を取り除いても $a_2$ を誤る」順列は $N\le5$ には無く、$N=6$ で最初に見つかったのが入力例 1
実行時間（実測、$N=2\times10^5$、負荷平均 8〜19）: ランダム順列 $K=1$ 0.38 s・$K=10$ 0.43 s・$K=30$ 1.14 s・$K=50$ 1.74 s・$K=100$ 3.74 s・全行 10.08 s。減少列 $K=50$ 0.78 s・$K=1000$ 13.08 s。450 個ずつのブロックを逆順に並べた列 $K=50$ 1.37 s
扱っていない範囲: 部分列の構成、重複ありの列、すべての $k$ の答えを高速に出す方法、原典の確認

自己評価

完全理解おおむね理解要復習

Day 172-Q3 — 2026-10-08 | k 本の増加部分列（Greene の定理。RSK の挿入表の上 k 行の長さの和が答え。上 K 行だけ持てば O(NK log N)）

問題