Day 160-Q4 — 2026-09-25 — Powersort の併合方針（CPython の list.sort が使う「run の中点の二進展開」による、ほぼ最適な併合順）

問題

長さ $N$ の整数列 $A$ が与えられる。$A$ を 極大な広義単調増加区間（run） $R_1,R_2,\dots,R_m$ に分ける（$A_{i}<A_{i-1}$ の位置で区切る）。$R_j$ の開始位置を $s_j$（0 始まり）、長さを $\ell_j$ とする。

隣り合う run $R_j,R_{j+1}$ の境界の power を次で定める。2 つの中点 $a=(s_j+\ell_j/2)/N$、$b=(s_{j+1}+\ell_{j+1}/2)/N$ に対し

$$\mathrm{power}_j=\min\{k\ge1 : \lfloor a\cdot2^k\rfloor\ne\lfloor b\cdot2^k\rfloor\}$$

次の手順（Powersort, Munro–Wild 2018）で run を併合する。長さ $x$ と $y$ の列の併合のコストを $x+y$ とし、コストの総和 を出力せよ。

cur = R_1;  stack = []
for j = 1 .. m-1:
    p = power_j
    while stack が空でなく、stack の一番上の power > p:
        top = stack.pop();  cur = merge(top, cur)
    stack.push((cur, p));  cur = R_{j+1}
while stack が空でない:
    top = stack.pop();  cur = merge(top, cur)

入力形式

N
A_1 A_2 ... A_N

制約

入出力例

15
1 2 3 4 5 6 7 2 3 4 5 6 3 2 1

28

（run の長さは 7, 5, 1, 1, 1。中点は $3.5/15=0.233$、$9.5/15=0.633$、$0.833$、$0.900$、$0.967$。境界 1 は 0.5 をまたぐので power 1、境界 2 は 0.75 をまたいで 2、境界 3 は 0.875 で 3、境界 4 は 0.9375 で 4。power が右へ単調に増えるので全部積まれ、右から $1+1=2$、$1+2=3$、$5+3=8$、$7+8=15$ と併合してコスト 28。これは最適な併合順のコスト 28 と一致する。Timsort の併合規則では 38、隣同士を 2 つずつ併合する素朴な方式では 43）

Powersort は J. Ian Munro, Sebastian Wild「Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs」（ESA 2018、https://arxiv.org/abs/1805.04154 、2026-09-25 参照）の手法で、CPython の Objects/listsort.txt（https://github.com/python/cpython/blob/main/Objects/listsort.txt 、同上参照）に「The code now uses the "powersort" merge strategy」とあり、list.sort()／sorted() の併合順に使われている（導入は bpo-34561）。

概念図：power と併合木

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

def node_power(s1, n1, n2, n):
    a = 2 * s1 + n1               # 中点 × 2（分母 2n）で整数化
    b = 2 * (s1 + n1) + n2
    k = 0
    while True:
        k += 1
        if (a << k) // (2 * n) != (b << k) // (2 * n):
            return k

模範解答 (Python)

📋 コピーimport sys


def node_power(s1, n1, n2, n):
    """境界の power: 2 つの run の中点 a, b（[0,1) に正規化）の二進展開が初めて食い違う桁。"""
    a = 2 * s1 + n1            # 中点×2（分母 2n）
    b = 2 * (s1 + n1) + n2
    k = 0
    while True:
        k += 1
        # floor(a * 2^k / 2n) と floor(b * 2^k / 2n) が異なる最小の k
        if (a << k) // (2 * n) != (b << k) // (2 * n):
            return k


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    A = list(map(int, data[1:1 + n]))
    # 1) 極大な広義単調増加 run に分解
    runs = []            # (開始位置, 長さ)
    s = 0
    for i in range(1, n + 1):
        if i == n or A[i] < A[i - 1]:
            runs.append((s, i - s))
            s = i
    # 2) Powersort の併合方針。コスト = 併合した 2 列の長さの和の総和
    cost = 0
    stack = []           # (開始位置, 長さ, 右隣との境界の power)
    cs, cl = runs[0]
    for bs, bl in runs[1:]:
        p = node_power(cs, cl, bl, n)
        while stack and stack[-1][2] > p:   # 深い（power が大きい）境界から先に併合
            ts, tl, _ = stack.pop()
            cost += tl + cl
            cs, cl = ts, tl + cl
        stack.append((cs, cl, p))
        cs, cl = bs, bl
    while stack:
        ts, tl, _ = stack.pop()
        cost += tl + cl
        cs, cl = ts, tl + cl
    print(cost)


main()

Step-by-Step 解説

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

前提が変わったら: 本問は run の検出を単純化している。実際の list.sort は (1) 狭義減少の run を反転して使う (2) 短い run を二分挿入ソートで最小長 minrun まで伸ばす (3) 併合中に galloping で比較回数を減らす。入力がほぼランダムなら run は短く、コストの差はほぼ出ない（$N=2\times10^5$ の乱数で run は約 $10^5$ 本）。

よくあるミス

次のステップ

• 発展1: 最適な併合木（Garsia–Wachs）と Powersort の木を同じ入力で描き、深さが違う run を特定する
• 発展2: Timsort の merge_collapse（修正版）を実装し、本問の入力例で 38 になることを確かめる。さらに 2015 年の修正前の条件（直前 3 本だけを見る）で不変条件が壊れる入力を探す
• 扱わなかった範囲: galloping mode、minrun の決め方（listsort.txt には 2025 年の新方式の記述がある）、比較回数の解析

自己評価

自分の回答

気づき・メモ