Day 023-Q1 | SMAWK Algorithm

問題

$N \times M$ の行列 $A$ が与えられる。この行列は totally monotone である（各行の最小値を取る列インデックスが単調非減少）。各行の最小値のインデックス（0-indexed）を求めよ。

具体的な問題として、以下の行列を考える（$N=5, M=6$）:

$$A[i][j] = (i - j)^2 + i \cdot j \bmod 7$$

各行の最小値を取る列インデックスを求めよ。

入力形式

N M

制約

$1 \le N, M \le 1000$（この問題の実装では）

行列は totally monotone を満たす

入出力例

入力例 1

5 6

出力例 1

0 1 2 2 3

各行の最小値を取る列インデックス、空白区切り。

ヒント (段階的開示)

ヒント1: 方向性

Totally monotone 行列では、各行の最小値列インデックスが単調非減少という性質を使う。ナイーブ実装は $O(NM)$ だが、SMAWK Algorithm は $O(N+M)$ で解ける。

ヒント2: アプローチ

SMAWK の核心は「Reduce」ステップ。$M$ 列から $N$ 列を選ぶ際、ある列 $c$ が列 $c'$（$c < c'$）に「支配される」条件を利用して候補列を削減できる。Reduce 後に再帰的に奇数行を処理し、偶数行を補間する。

ヒント3: 誘導

def smawk(rows, cols, lookup):
    # Reduce: 候補列を削減
    def reduce(rows, cols):
        stack = []
        for col in cols:
            while stack and lookup(rows[len(stack)-1], stack[-1]) >= lookup(rows[len(stack)-1], col):
                stack.pop()
            if len(stack) < len(rows):
                stack.append(col)
        return stack
    # 再帰的に奇数インデックス行を処理
    # 偶数インデックス行を補間
    ...

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())

    def val(i, j):
        return (i - j) ** 2 + (i * j) % 7

    def smawk_internal(rows, cols, ans):
        if not rows:
            return

        # Reduce
        stk = []
        for col in cols:
            while stk and val(rows[len(stk) - 1], stk[-1]) >= val(rows[len(stk) - 1], col):
                stk.pop()
            if len(stk) < len(rows):
                stk.append(col)
        cols = stk

        # 奇数行再帰
        odd_rows = rows[1::2]
        smawk_internal(odd_rows, cols, ans)

        # 偶数行補間
        j = 0
        for i in range(0, len(rows), 2):
            row = rows[i]
            if i + 1 < len(rows):
                next_odd = rows[i + 1]
                end = cols.index(ans[next_odd]) + 1 if next_odd in ans else len(cols)
            else:
                end = len(cols)

            best_val = float('inf')
            best_col = cols[j]
            while j < end:
                v = val(row, cols[j])
                if v < best_val:
                    best_val = v
                    best_col = cols[j]
                j += 1
            ans[row] = best_col
            if i + 1 < len(rows):
                j = cols.index(ans[rows[i]])  # reset for next even row

    ans = {}
    smawk_internal(list(range(N)), list(range(M)), ans)
    print(*[ans[i] for i in range(N)])

solve()

Step-by-Step 解説

1Totally Monotone 行列の性質
行列 $A$ が totally monotone とは、各行 $i$ の最小値を達成する最左列インデックスを $\text{opt}(i)$ とすると: $\text{opt}(0) \le \text{opt}(1) \le \cdots \le \text{opt}(N-1)$。この単調性が SMAWK の核心。

2Reduce ステップ
$M > N$ のとき、$M$ 列から $N$ 列に削減する。列 $c$ が列 $c'$（$c < c'$）に支配される条件: $\exists \text{ row } r : A[r][c] \ge A[r][c'] \text{ かつ } c < c'$。スタックを使って $O(N + M)$ で実行。

3分割統治
削減後、奇数インデックスの行のみを再帰処理（行数が半分）。偶数行は奇数行の結果を境界として線形スキャン。計算量: $T(N, M) = T(N/2, N) + O(N + M) = O(N + M)$

よくあるミス

ミス	原因	正しい書き方
Totally monotone を確認しない	行列の性質を誤解	問題文の条件を必ず確認
Reduce ステップのスタック条件ミス	支配関係の向きを誤る	`val(rows[len(stack)-1], stack[-1]) >= val(rows[len(stack)-1], col)`
列インデックスの検索に O(M)	`cols.index()` を多用	dict や pointer で O(1) に

次のステップ

発展問題: Li Chao Tree との組み合わせ（SMAWK + CHT による DP 最適化）
「Concave SMAWK」（totally monotone でなく concave の場合）
AtCoder Library の monotone_minima 関数の内部実装を読む

自己評価

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

Day 023-Q1 — SMAWK Algorithm（全行最小値の高速計算）

問題