Section 4 まではデータ構造の選択・前処理・スライディングウィンドウを扱いました。
Section 5 では「問題の解き方そのもの」を設計します。
前半（問題 29〜34）は分割統治と再帰の改善です。
「問題を半分に分割することで指数から対数に落とす」という発想を、フィボナッチ・GCD・べき乗・素数・LIS・KMP という具体的な問題を通して身につけます。
後半（問題 35〜42）は動的計画法です。
「同じ部分問題を何度も解く再帰」をメモ化で O(n) に改善するところから始め、2次元 DP テーブル・ローリング配列による空間削減・更新方向によるセマンティクスの変化と段階的に進みます。
グラフの連結成分・最短路もここで扱います。
問題 33（LIS）は Section 3 で学んだ二分探索と Section 5 の DP が融合する問題です。
問題 34（KMP）は Section 4 の「前処理で後の操作を速くする」と同じ構造を持ちます。
1. 分割統治と再帰の改善（問題 29〜34）
2. 問題29 フィボナッチ数の計算
非負整数 n を受け取り、第 n フィボナッチ数を返す関数を書いてください。
F(0)=0、F(1)=1、F(n)=F(n-1)+F(n-2) と定義します。
入力: n = 0 → 0
入力: n = 1 → 1
入力: n = 5 → 5 (0 1 1 2 3 5)
入力: n = 10 → 55
入力: n = 30 → 832040Code language: HTTP (http)素直な再帰は O(φⁿ) の指数時間になります。(fib-naive 40) は数秒かかりますが、メモ化や反復で O(n) になります。
分割統治の前に「重複する部分問題」の問題を見ておきます。
これを解決する技法（メモ化・反復）が後半の動的計画法（問題35〜42）の基盤になります。
2.1. 素直な実装 — O(2ⁿ)
(defun fib-naive (n)
"単純な再帰。同じ部分問題を指数回計算する。"
(if (< n 2)
n
;; fib(n-1) と fib(n-2) は独立に再帰するため
;; fib(n-1) の中でも fib(n-2) が計算される。
;; fib(5) の呼び出し木で fib(2) だけで 3 回計算される。
(+ (fib-naive (- n 1))
(fib-naive (- n 2)))))Code language: Lisp (lisp)2.2. 効く実装1：メモ化 — O(n)
(defun fib-memo (n)
"メモ化で部分問題の再計算を防ぐ。"
(let ((cache (make-array (+ n 1) :initial-element nil)))
(labels ((rec (k)
(cond
((< k 2) k)
;; キャッシュヒット：計算済みの値をそのまま返す。
((aref cache k))
(t
;; setf は代入した値を返すので (setf ...) 自体が戻り値になる。
(setf (aref cache k)
(+ (rec (- k 1)) (rec (- k 2))))))))
(rec n))))Code language: Lisp (lisp)2.3. 効く実装2：反復 — O(n) 時間・O(1) 空間
(defun fib-iter (n)
"2変数だけで O(n) 時間・O(1) 空間。"
(if (< n 2)
n
(loop with a = 0 and b = 1
repeat (- n 1)
do
;; psetf：「並行代入」。右辺をすべて評価してから左辺に代入する。
;; (psetf a b b (+ a b)) は
;; 新しい a ← 今の b
;; 新しい b ← 今の a + 今の b
;; を同時に行う。通常の setf で書くと一時変数が必要になる。
(psetf a b b (+ a b))
finally (return b))))Code language: Lisp (lisp)psetf がなぜ必要か：
;; 通常の setf では順番に代入されるため壊れる。
(let ((a 0) (b 1))
(setf a b) ; a ← 1
(setf b (+ a b))) ; b ← 1 + 1 = 2 ← a がもう書き換わっている！
;; a=1, b=2 （正しくは a=1, b=1）
;; psetf なら大丈夫。
右辺は元の a, b で評価される。
(let ((a 0) (b 1))
(psetf a b b (+ a b))) ; a ← 1, b ← 0+1=1
;; a=1, b=1 ✓Code language: Lisp (lisp)メモ化は「同じ引数で呼ばれうる純粋関数」に適用できます。
反復版はコールスタックを使わないため、大きな n でもスタックオーバーフローしません。
「直前の値だけ保持すればよい」という空間の削減は Kadane 法（問題27）と同じ発想です。
3. 問題30 最大公約数の計算
正の整数 a と b を受け取り、最大公約数を返す関数を書いてください。
入力: a = 48, b = 18 → 6
入力: a = 100, b = 75 → 25
入力: a = 17, b = 13 → 1 (互いに素)
入力: a = 12, b = 12 → 12Code language: HTTP (http)1から順に割ってみる素直な実装は O(min(a, b)) です。
ユークリッドの互除法は O(log(min(a, b))) で済みます。
Common Lisp の組み込み gcd を使えばよいですが、原理を知っておくと類似問題に応用できます。
問題29で「同じ問題を何度も解く再帰が遅い」ことを確認しました。
問題30は「賢い再帰（ユークリッドの互除法）」の例で、各ステップで問題が指数的に小さくなります。
3.1. 素直な実装 — O(min(a,b))
(defun gcd-naive (a b)
"1 から順に割ってみる。"
(loop for i from (min a b) downto 1
when (and (zerop (mod a i)) ; zerop は (= x 0) と同じ
(zerop (mod b i)))
return i))Code language: Lisp (lisp)3.2. 効く実装 — O(log(min(a,b)))
(defun gcd-euclid (a b)
"ユークリッドの互除法。"
;; 原理：gcd(a, b) = gcd(b, a mod b)
;; (a mod b) < b/2 を満たすため、2ステップごとに値が半分以下になる。
;; → ステップ数は O(log(min(a,b)))。
(if (zerop b)
a
(gcd-euclid b (mod a b))))
;; Common Lisp には gcd が組み込まれている。
;; (gcd 48 18) => 6
;; 複数引数：(gcd 12 18 24) => 6Code language: Lisp (lisp)各ステップで値が半分以下になるため、再帰深さは O(log n) です。
「問題サイズが毎ステップ半分になる」という性質が、問題31（べき乗）・問題32（エラトステネスの篩）・問題18（マージソート）に共通します。
4. 問題31 べき乗の計算
整数 base と非負整数 exponent を受け取り、base の exponent 乗を返す関数を書いてください。
入力: base = 2, exponent = 10 → 1024
入力: base = 3, exponent = 5 → 243
入力: base = 7, exponent = 0 → 1
入力: base = 2, exponent = 30 → 1073741824Code language: HTTP (http)繰り返し掛け算は O(n) ですが、繰り返し二乗法で O(log n) になります。
モジュラべき乗（べき乗を割った余り）はAtCoderの多くの問題で使われます。
問題30の「問題サイズが半分になる再帰」をべき乗に適用します。
指数関数時間から対数時間への変換です。
4.1. 素直な実装 — O(n)
(defun power-naive (base exponent)
(loop with result = 1
repeat exponent
do (setf result (* result base))
finally (return result)))Code language: Lisp (lisp)4.2. 効く実装 — O(log n)
(defun power-fast (base exponent)
"繰り返し二乗法（binary exponentiation）。"
(cond
((zerop exponent) 1)
;; evenp：偶数なら t を返す。oddp は奇数のとき t。
;; 偶数乗：base^n = (base^(n/2))^2
((evenp exponent)
;; half を2回書くと2回再帰してしまうので必ず let で保持する。
(let ((half (power-fast base (/ exponent 2))))
(* half half)))
;; 奇数乗：base^n = base × base^(n-1)
(t (* base (power-fast base (1- exponent))))))
;; 組み込みの expt が利用可能。
整数べき乗には最適化が入っている。
;; Common Lisp は多倍長整数をネイティブにサポート。
;; (expt 2 64) => 18446744073709551616 ← オーバーフローなしCode language: Lisp (lisp)exponent が半分になるたびに問題サイズが半分になるため再帰深さは O(log n) です。
この分割統治の構造はマージソート（問題18）と同じです。
5. 問題32 素数判定と篩
整数 n が素数かどうかを返す関数と、limit 以下のすべての素数をリストで返す関数を書いてください。
(prime-fast 2) → t
(prime-fast 17) → t
(prime-fast 18) → nil
(prime-fast 1) → nil
(sieve-of-eratosthenes 30)
→ (2 3 5 7 11 13 17 19 23 29)
(sieve-of-eratosthenes 10)
→ (2 3 5 7)Code language: Lisp (lisp)素数判定は O(n) から O(√n) に改善できます。
篩は n 以下の素数を全列挙する場合に O(n log log n) で動作し、n = 10^6 規模でも十分高速です。
問題30・31で「各ステップで問題が半分になる」パターンを確認しました。
問題32は「探索範囲を √n に限定できる」という数学的性質の活用です。
5.1. 素数判定 — O(√n)
(defun prime-fast (n)
"√n までしか調べない。"
;; 理由：n = a × b のとき、a ≤ b なら a ≤ √n。
;; → √n より大きな因数があれば対の因数が √n 以下にある。
;;
;; isqrt：整数の床平方根。floor(sqrt(n)) に相当だが誤差なし。
;; (isqrt 10) => 3、浮動小数点の sqrt とは違い正確。
(when (>= n 2)
(if (= n 2)
t
(and (oddp n)
(loop for i from 3 to (isqrt n) by 2
never (zerop (mod n i)))))))Code language: Lisp (lisp)5.2. エラトステネスの篩 — O(n log log n)
(defun sieve-of-eratosthenes (limit)
"ビットベクタで篩を実装する。"
;; make-array の :element-type 'bit はビット配列を作る。
;; 各要素は 0 か 1 のみ。1要素 = 1ビットなので通常の配列の1/64のメモリ。
;; キャッシュに収まりやすく実際の速度も向上する。
(let ((composite (make-array (1+ limit)
:element-type 'bit
:initial-element 0)))
(setf (aref composite 0) 1
(aref composite 1) 1)
(loop for p from 2 to (isqrt limit) do
(when (zerop (aref composite p))
;; p² から始める理由：p より小さい素数 q について
;; q × p はすでに q の倍数としてマーク済み。
(loop for m from (* p p) to limit by p do
(setf (aref composite m) 1))))
(loop for i from 2 to limit
when (zerop (aref composite i))
collect i)))
;; (sieve-of-eratosthenes 30) => (2 3 5 7 11 13 17 19 23 29)Code language: Lisp (lisp)isqrt は浮動小数点誤差なしに整数の平方根を求めます。element-type 'bit はメモリ効率の高い配列を作ります。
「どこまで探索すれば十分か」という数学的な境界を知ることが、アルゴリズムの改善に直結します。
6. 問題33 最長増加部分列（LIS）— O(n²) と O(n log n)
整数ベクタ seq を受け取り、狭義単調増加な部分列（要素を選んで取り出したもの）の最大長を返す関数を書いてください。
入力: seq = #(3 1 4 1 5 9 2 6 5 3 5)
出力: 4 ← (1 4 5 9) や (1 2 6) など複数の正解がある
入力: seq = #(1 2 3 4 5)
出力: 5
入力: seq = #(5 4 3 2 1)
出力: 1
入力: seq = #(10 9 2 5 3 7 101 18)
出力: 4 ← (2 3 7 101) または (2 5 7 101)Code language: PHP (php)AtCoder の頻出問題の一つです。
DP で O(n²)、二分探索を組み合わせると O(n log n) になります。
問題19（二分探索）と問題29〜31の技術が組み合わさる問題です。
「ソート済み配列への二分探索で状態を更新する」という と の融合です。
6.1. 素直な実装 — O(n²) DP
(defun lis-dp (seq)
"各位置で、それ以前の要素との比較によって DP テーブルを埋める。"
(let* ((n (length seq))
;; dp[i] = seq[i] を末尾とする最長増加部分列の長さ。
;; 各要素は単独で長さ 1 なので初期値は 1。
(dp (make-array n :initial-element 1)))
(loop for i from 1 below n do
(loop for j from 0 below i do
(when (< (aref seq j) (aref seq i))
(setf (aref dp i) (max (aref dp i) (1+ (aref dp j)))))))
(reduce #'max dp)))Code language: Lisp (lisp)6.2. 効く実装 — O(n log n)
(defun lower-bound (vec len x)
"vec[0..len) の中で x 以上の最初のインデックスを二分探索で返す。"
(let ((lo 0) (hi len))
(loop while (< lo hi) do
;; ash：算術ビットシフト。
(ash x -1) = floor(x/2)。
;; 乗除算より高速で、整数除算の標準的な書き方。
(let ((mid (ash (+ lo hi) -1)))
(if (< (aref vec mid) x)
(setf lo (1+ mid))
(setf hi mid))))
lo))
(defun lis-fast (seq)
"patience sorting の変形。tails 配列を二分探索で管理する。"
;; tails[i] = 長さ (i+1) の増加部分列の末尾の最小値。
;; 不変条件：tails は常に狭義単調増加 → 二分探索できる。
;;
;; fill-pointer を指定すると「論理的なサイズ」を持つベクタを作れる。
;; vector-push で fill-pointer の位置に要素を追加して +1 する。
(let ((tails (make-array (length seq)
:element-type 'fixnum
:fill-pointer 0)))
(loop for x across seq do
(let ((pos (lower-bound tails (fill-pointer tails) x)))
(if (= pos (fill-pointer tails))
;; tails を延長できる。
(vector-push x tails)
;; tails[pos] を x で置き換える（末尾値を小さく保つ）。
(setf (aref tails pos) x))))
(fill-pointer tails)))Code language: Lisp (lisp)tails は単調増加を維持するため lower-bound で位置を O(log n) で特定できます。fill-pointer を使うと固定長配列を可変長として使えます。
「二分探索で単調配列を維持する」という設計は問題19（二分探索）の自然な応用です。
7. 問題34 文字列の部分一致検索（KMP）
文字列 text と pattern を受け取り、pattern が text に出現する開始インデックスをすべて返す関数を書いてください。
入力: text = "ababcababc"
pattern = "ababc"
出力: (0 5)
入力: text = "aaaaaa"
pattern = "aaa"
出力: (0 1 2 3) ← 重複を含む
入力: text = "hello"
pattern = "world"
出力: ()
入力: text = "mississippi"
pattern = "issi"
出力: (1 4)Code language: JavaScript (javascript)素直な実装は O(nm)、KMP アルゴリズムで O(n + m) になります。
n = 10^5、m = 10^4 規模では差が顕著です。
問題30〜33の「賢い分割・探索」の締めくくりとして、KMP アルゴリズムを扱います。
失敗しても最初からやり直さないというパターン一致の賢さが核心です。
7.1. 素直な実装 — O(nm)
(defun naive-search (text pattern)
"各位置から照合を試みる。"
(let ((n (length text))
(m (length pattern))
(results '()))
(loop for i from 0 to (- n m) do
;; string= の :start1 :end1 でコピーなしの部分照合。
(when (string= text pattern :start1 i :end1 (+ i m))
(push i results)))
(nreverse results)))Code language: Lisp (lisp)7.2. KMP アルゴリズム — O(n + m)
(defun build-failure-function (pattern)
"KMP の失敗関数（partial match table）を構築する。O(m)。"
;; failure[i] の意味：
;; pattern[0..i] の「真の接頭辞かつ真の接尾辞」の最長の長さ。
;;
;; 例：pattern = "ababc"
;; i=2: "aba" → "a" が共通 → failure[2] = 1
;; i=3: "abab" → "ab" が共通 → failure[3] = 2
;; i=4: "ababc" → 共通なし → failure[4] = 0
(let* ((m (length pattern))
(failure (make-array m :initial-element 0))
(k 0))
(loop for i from 1 below m do
;; char/=：2文字が異なるか判定する。
(not (char= ...)) と同じ。
(loop while (and (> k 0)
(char/= (char pattern k) (char pattern i)))
do (setf k (aref failure (1- k))))
(when (char= (char pattern k) (char pattern i))
(incf k))
(setf (aref failure i) k))
failure))
(defun kmp-search (text pattern)
"KMP アルゴリズムでパターンを検索する。O(n + m)。"
(let* ((n (length text))
(m (length pattern))
(failure (build-failure-function pattern))
(k 0)
(results '()))
(loop for i from 0 below n do
;; 不一致のとき失敗関数で k を巻き戻す。テキストポインタ i は後退しない。
(loop while (and (> k 0)
(char/= (char pattern k) (char text i)))
do (setf k (aref failure (1- k))))
(when (char= (char pattern k) (char text i))
(incf k))
(when (= k m)
(push (- i m -1) results)
(setf k (aref failure (1- k)))))
(nreverse results)))
;; 使用例
;; (kmp-search "ababcababc" "ababc") => (0 5)
;; (kmp-search "aaaaaa" "aaa") => (0 1 2 3)Code language: PHP (php)KMP の直感的な説明：
text = a b a b c a b a b c
pattern = a b a b c
↑不一致（仮）
朴訥な探索：text を1つ進めて最初から照合し直す。
KMP：pattern 内で "abab" の「最長の接頭辞=接尾辞」が "ab"（長さ2）なので、
パターンを2文字分進めた位置から再開できる。text を巻き戻さない。Code language: JavaScript (javascript)失敗関数はパターン自身の「自己一致」の情報を O(m) で事前計算します。
「前処理で後の操作を速くする」という Section 4 の発想と同じ構造です。
8. 動的計画法（問題 35〜42）
問題29（フィボナッチ）のメモ化で「同じ部分問題を何度も解く再帰」を O(n) に改善しました。
ここではその発展として、2次元の部分問題テーブル・ローリング配列による空間削減・テーブルの「降順更新と昇順更新」という DP 特有の設計判断を扱います。
9. 問題35 最長共通部分列（LCS）
文字列 s1 と s2 を受け取り、両方に共通する部分列（連続でなくてよい）の最大長を返す関数を書いてください。
入力: s1 = "abcde"
s2 = "ace"
出力: 3 ← "ace"
入力: s1 = "abc"
s2 = "abc"
出力: 3
入力: s1 = "abc"
s2 = "def"
出力: 0
入力: s1 = "aggtab"
s2 = "gxtxayb"
出力: 4 ← "gtab"Code language: JavaScript (javascript)diff コマンドや DNA 配列の比較で使われる古典的な問題です。
メモ化なしの再帰は指数時間になります。
DP テーブルで O(mn) になり、ローリング配列で空間を O(n) に削減できます。
問題29（フィボナッチ）は1次元の部分問題でした。
問題35は「2つの文字列の位置の組 (i, j)」という2次元の部分問題になります。
9.1. 素直な実装 — O(2^(m+n))
(defun lcs-naive (s1 s2 i j)
"メモ化なし再帰。同じ (i, j) が指数回呼ばれる。"
(cond
((or (zerop i) (zerop j)) 0)
((char= (char s1 (1- i)) (char s2 (1- j)))
(1+ (lcs-naive s1 s2 (1- i) (1- j))))
(t (max (lcs-naive s1 s2 (1- i) j)
(lcs-naive s1 s2 i (1- j))))))Code language: Lisp (lisp)9.2. 効く実装 — O(mn) DP
(defun lcs-dp (s1 s2)
"2次元 DP テーブルで O(mn) 時間。"
(let* ((m (length s1))
(n (length s2))
;; 2次元配列を作る。make-array に (list 行 列) を渡す。
;; (aref dp i j) でアクセスする。
(dp (make-array (list (1+ m) (1+ n)) :initial-element 0)))
(loop for i from 1 to m do
(loop for j from 1 to n do
(setf (aref dp i j)
(if (char= (char s1 (1- i)) (char s2 (1- j)))
;; 一致：左上 dp[i-1][j-1] に +1。
(1+ (aref dp (1- i) (1- j)))
;; 不一致：上か左の大きいほう。
(max (aref dp (1- i) j)
(aref dp i (1- j)))))))
(aref dp m n)))Code language: Lisp (lisp)空間 O(n) に削減する版（ローリング配列）：
(defun lcs-space-optimized (s1 s2)
"1行分のテーブルだけ保持する。O(n) 空間。"
(let* ((m (length s1))
(n (length s2))
(prev (make-array (1+ n) :initial-element 0))
(curr (make-array (1+ n) :initial-element 0)))
(loop for i from 1 to m do
(loop for j from 1 to n do
(setf (aref curr j)
(if (char= (char s1 (1- i)) (char s2 (1- j)))
(1+ (aref prev (1- j)))
(max (aref prev j) (aref curr (1- j))))))
;; rotatef：複数の場所の値を巡回交換する。
;; (rotatef a b) は a と b を交換する。配列のコピーは発生しない。O(1)。
(rotatef prev curr)
;; fill：配列の全要素を指定値で上書きする。
(fill curr 0))
(aref prev n)))Code language: Lisp (lisp)rotatef の動作：
rotatef 前: prev → [配列A] curr → [配列B]
rotatef 後: prev → [配列B] curr → [配列A]
ポインタが交換されるだけで配列の中身はコピーされない。O(1)。Code language: CSS (css)DP テーブルは「前の行だけ参照する」なら2行に削減でき、rotatef でコピーなしに使い回せます。
10. 問題36 0/1 ナップサック問題
重さのベクタ weights、価値のベクタ values、重量制限 capacity を受け取り、合計重量が capacity 以下になるようにアイテムを選んだときの最大価値を返す関数を書いてください。
各アイテムは1回しか使えません。
入力: weights = #(2 3 4 5)
values = #(3 4 5 6)
capacity = 8
出力: 10 ← 重さ3+5=8、価値4+6=10
入力: weights = #(1 2 3)
values = #(6 10 12)
capacity = 5
出力: 22 ← 重さ2+3=5、価値10+12=22
入力: weights = #(10)
values = #(100)
capacity = 5
出力: 0 ← 入らないCode language: PHP (php)典型的な DP 問題で、AtCoder の多くの問題の基礎になっています。
DP テーブルを降順に更新することで O(nW) になります。
問題35は「テーブルを2行に削減した」でした。
問題36は「2次元テーブルを1次元に削減する」かつ「更新の方向」が正しさに影響するという、DP 特有の設計判断を扱います。
10.1. 素直な実装 — O(2^n)
(defun knapsack-naive (items capacity)
"全組み合わせを試す。items = ((weight . value) ...)。"
(labels ((rec (remaining cap)
(if (null remaining)
0
(let* ((item (car remaining))
(rest (cdr remaining))
(w (car item))
(v (cdr item)))
(if (> w cap)
(rec rest cap)
(max (rec rest cap)
(+ v (rec rest (- cap w)))))))))
(rec items capacity)))Code language: Lisp (lisp)10.2. 効く実装 — O(nW)
(defun knapsack-dp (weights values capacity)
"1次元 DP テーブル。W を降順に更新することで 0/1 制約を満たす。"
(let ((n (length weights))
(dp (make-array (1+ capacity) :initial-element 0)))
(loop for i from 0 below n do
(let ((w (aref weights i))
(v (aref values i)))
;; 容量を大きいほうから更新する（降順）。
;; 理由：dp[c - w] は「アイテム i を追加する前の状態」を参照したい。
;; 降順ならば c - w < c なのでまだ更新されていない。
;; 昇順にすると dp[c - w] が「アイテム i をすでに追加した後」になり
;; 同じアイテムを2回使える無制限ナップサックになる。
(loop for c from capacity downto w do
(setf (aref dp c)
(max (aref dp c)
(+ (aref dp (- c w)) v))))))
(aref dp capacity)))Code language: Lisp (lisp)「降順更新で 0/1、昇順更新で無制限」は DP の頻出知識です。
コードの見た目は downto が to になるだけですが、意味がまったく変わります。
11. 問題37 コイン変換問題（最小枚数）
整数のリスト coins と目標金額 amount を受け取り、coins を何枚でも組み合わせて amount ちょうどを作るのに必要な最小枚数を返す関数を書いてください。
作れない場合は -1 を返します。
入力: coins = (1 5 10 25)
amount = 36
出力: 3 ← 25 + 10 + 1
入力: coins = (1 5 10 25)
amount = 30
出力: 2 ← 25 + 5
入力: coins = (2)
amount = 3
出力: -1 ← 奇数は作れないAtCoder の DP 入門問題として頻出です。
DP テーブルを昇順に更新することでコインを何枚でも使える設計になります。
問題36（0/1 ナップサック）と構造は似ていますが、各コインは何枚でも使えます。
昇順更新で無制限ナップサックの設計を正面から使います。
(defun min-coins (coins amount)
"DP でボトムアップに解く。"
;; dp[a] = 金額 a を作るのに必要な最小枚数。
;; 初期値 (1+ amount)：「作れない」を表す番兵。
;; most-positive-fixnum ではなく上界として amount+1 を使うのが安全。
;; （(1+ most-positive-fixnum) がオーバーフローする可能性を避ける）
(let ((dp (make-array (1+ amount) :initial-element (1+ amount))))
(setf (aref dp 0) 0)
;; a を 1 から amount まで昇順に更新する。
;; dp[a - coin] は「このコインを使って残り (a - coin) を作る最小枚数」。
;; 昇順更新なので dp[a - coin] はすでに確定している。
;; これは「同じコインを何枚でも使える」無制限ナップサック。
(loop for a from 1 to amount do
(dolist (coin coins)
(when (<= coin a)
(setf (aref dp a)
(min (aref dp a)
(1+ (aref dp (- a coin))))))))
(if (> (aref dp amount) amount) -1 (aref dp amount))))
;; 使用例
;; (min-coins '(1 5 10 25) 36) => 3 (25 + 10 + 1)
;; (min-coins '(2) 3) => -1 (奇数は作れない)Code language: Lisp (lisp)問題36（downto）と問題37（to）を並べると、更新の方向がセマンティクスを決めることがよく見えます。
問題36と37はセットで理解してください。
12. 問題38 編集距離（レーベンシュタイン距離）
文字列 a と b を受け取り、a を b に変換するのに必要な最小の操作回数を返す関数を書いてください。
操作は「1文字の挿入」「1文字の削除」「1文字の置換」で、それぞれコスト1です。
入力: a = "kitten"
b = "sitting"
出力: 3 ← k→s, e→i, +g
入力: a = "sunday"
b = "saturday"
出力: 3
入力: a = "abc"
b = "abc"
出力: 0
入力: a = ""
b = "abc"
出力: 3 ← 3回挿入Code language: JavaScript (javascript)スペルチェッカーや diff ツール、DNA 配列のアライメントで使われます。
メモ化なしの再帰は指数時間になります。
ローリング配列で O(n) 空間の DP になります。
問題35（LCS）と同じ2次元 DP ですが、遷移が上・左・左上の3方向あります。
問題35で学んだローリング配列パターンをそのまま適用できます。
12.1. 素直な実装 — 指数時間
(defun edit-distance-naive (a b)
(labels ((rec (i j)
(cond ((= i 0) j)
((= j 0) i)
((char= (char a (1- i)) (char b (1- j)))
(rec (1- i) (1- j)))
(t (1+ (min (rec (1- i) j)
(rec i (1- j))
(rec (1- i) (1- j))))))))
(rec (length a) (length b))))12.2. 効く実装 — O(mn) DP、O(n) 空間
(defun edit-distance-fast (a b)
"ローリング配列で O(n) 空間。"
(let* ((m (length a))
(n (length b))
(prev (make-array (1+ n)))
(curr (make-array (1+ n))))
;; 初期化：s1 が空なら s2 の長さ分の挿入が必要。
(loop for j from 0 to n do (setf (aref prev j) j))
(loop for i from 1 to m do
(setf (aref curr 0) i) ; s2 が空なら i 回削除
(loop for j from 1 to n do
(setf (aref curr j)
(if (char= (char a (1- i)) (char b (1- j)))
;; 一致：操作不要。左上の値をそのまま使う。
(aref prev (1- j))
;; 不一致：3操作のうち最小コスト + 1。
(1+ (min (aref prev j) ; 削除
(aref curr (1- j)) ; 挿入
(aref prev (1- j))))))) ; 置換
(rotatef prev curr))
(aref prev n)))
;; 使用例
;; (edit-distance-fast "kitten" "sitting") => 3Code language: Lisp (lisp)DP テーブルのイメージ：
"" s i t t i n g
"" 0 1 2 3 4 5 6 7
k 1 1 2 3 4 5 6 7
i 2 2 1 2 3 4 5 6
t 3 3 2 1 2 3 4 5
t 4 4 3 2 1 2 3 4
e 5 5 4 3 2 2 3 4
n 6 6 5 4 3 3 2 3
↑ answer = 3Code language: JavaScript (javascript)rotatef と fill の組み合わせで LCS・ナップサック・編集距離のすべてに同じローリング配列パターンが使えます。
13. 問題39 二分木の高さ
二分木の根ノードを受け取り、木の高さを返す関数を書いてください。
空の木の高さは 0 とします。
入力: 1
/ \
2 3
/ \
4 5
出力: 3
入力: 1
\
2
\
3
出力: 3
入力: (空の木)
出力: 0
入力: 単一ノード
出力: 1再帰版は実装がシンプルですが、SBCL のデフォルトスタックでは深さ 10^4 程度でスタックオーバーフローします。
BFS で反復実装するとヒープを使うためスタックが問題になりません。
DP の章に木を置いたのは「再帰の深さ」問題を扱うためです。
問題29（フィボナッチ）と同様に深い再帰はスタックを消費するという問題があり、その解決策として反復 BFS を紹介します。
(defstruct node val left right)Code language: Lisp (lisp)13.1. 素直な実装 — 再帰版（スタック危険）
(defun tree-height-naive (tree)
"シンプルな再帰。深い木でスタックオーバーフローのリスク。"
(if (null tree)
0
(1+ (max (tree-height-naive (node-left tree))
(tree-height-naive (node-right tree))))))
;; SBCL のデフォルトスタックサイズは 2MB。
;; 深さ 10^4〜10^5 の木で control-stack-exhausted エラーになる。Code language: Lisp (lisp)13.2. 効く実装 — 反復 BFS（スタック安全）
(defun tree-height-bfs (tree)
"幅優先探索でヒープを使う。スタック深さは O(幅) に留まる。"
(if (null tree)
0
(let ((queue (list tree))
(height 0))
(loop while queue do
(incf height)
;; 現在レベルの全ノードを展開して次レベルを queue に入れる。
(setf queue
(loop for node in queue
when (node-left node) collect (node-left node)
when (node-right node) collect (node-right node))))
height)))Code language: Lisp (lisp)再帰版はアルゴリズムとして O(n) で最適ですが、スタック深さが木の高さに比例するため深い木で問題になります。
BFS はキューをヒープ上に持つのでスタック深さが O(幅) に留まります。
付録 A（スタックサイズ拡張）の必要性ともつながっています。
14. 問題40 BST（二分探索木）の検索と平衡性
整数のリスト lst から二分探索木を構築し、指定した値が存在するかを O(log n) で返す関数を書いてください。
入力: lst = (5 3 7 1 4 6 8)
key = 4
出力: t
入力: lst = (5 3 7 1 4 6 8)
key = 9
出力: nil
入力: lst = (1 2 3 4 5) ← ソート済みで挿入すると最悪ケース
key = 3
出力: t (ただし木が右に偏って検索は O(n) に退化)ソート済みリストをそのまま挿入すると「右に伸びるだけの連結リスト」になり、検索が O(n) に退化します。
シャッフルしてから挿入すると期待 O(log n) の木が得られます。
問題33（LIS）で「ソート済み配列への二分探索」を確認しました。
問題40は「木構造における二分探索」を扱い、「入力の順序が性能に影響する」という BST 特有の問題を確認します。
(defstruct bst-node key left right)
(defun bst-insert (tree key)
"BST への挿入。平衡なら O(log n)、最悪 O(n)。"
(if (null tree)
(make-bst-node :key key)
(cond
((< key (bst-node-key tree))
(make-bst-node :key (bst-node-key tree)
:left (bst-insert (bst-node-left tree) key)
:right (bst-node-right tree)))
((> key (bst-node-key tree))
(make-bst-node :key (bst-node-key tree)
:left (bst-node-left tree)
:right (bst-insert (bst-node-right tree) key)))
(t tree))))
(defun bst-search (tree key)
(when tree
(let ((k (bst-node-key tree)))
(cond ((= key k) t)
((< key k) (bst-search (bst-node-left tree) key))
(t (bst-search (bst-node-right tree) key))))))Code language: Lisp (lisp)ソート済み入力で退化する問題と対策：
;; ソート済みリストをそのまま挿入すると右に偏った連結リスト状になる。
;; 検索が O(n) に退化する。
;; シャッフルで期待 O(log n) の木を作る。
(defun build-bst-shuffled (lst)
(let* ((n (length lst))
(vec (coerce lst 'vector)))
;; Fisher-Yates シャッフル：O(n) で全順列を等確率に生成する。
(loop for i from (1- n) downto 1 do
(let ((j (random (1+ i))))
;; rotatef で隣接要素を交換。一時変数不要。
(rotatef (aref vec i) (aref vec j))))
(reduce #'bst-insert (coerce vec 'list) :initial-value nil)))Code language: Lisp (lisp)BST は入力の順序に性能が大きく依存します。
本番では cl-containers ライブラリの平衡木を使うか、問題6〜12 で確認したハッシュテーブルで代替することを検討してください。
15. 問題41 グラフの連結成分（DFS と Union-Find）
頂点数 n と辺のリスト edges を受け取り、連結成分の個数を返す関数を書いてください。
入力: n = 6
edges = ((0 1) (1 2) (3 4))
出力: 3 ← {0,1,2}, {3,4}, {5}
入力: n = 4
edges = ((0 1) (1 2) (2 3))
出力: 1 ← すべて連結
入力: n = 5
edges = ()
出力: 5 ← 辺がないので全頂点が独立
入力: n = 3
edges = ((0 1) (1 2) (0 2))
出力: 1DFS と Union-Find の両方で O(V + E) です。
Union-Find は辺を動的に追加しながら「この時点での成分数」を問い合わせるオンライン処理に向いています。
(defun make-graph (n edges)
"隣接リストでグラフを作る。"
(let ((graph (make-array n :initial-element nil)))
(dolist (edge edges graph)
(destructuring-bind (u v) edge
(push v (aref graph u))
(push u (aref graph v))))))Code language: Lisp (lisp)15.1. DFS — O(V + E)
(defun count-components-dfs (graph)
(let* ((n (length graph))
(visited (make-array n :initial-element nil))
(count 0))
(labels ((dfs (v)
(setf (aref visited v) t)
(dolist (neighbor (aref graph v))
(unless (aref visited neighbor)
(dfs neighbor)))))
(dotimes (v n count)
(unless (aref visited v)
(incf count)
(dfs v))))))Code language: Lisp (lisp)15.2. Union-Find — 実質 O(V + E)
(defun make-uf (n)
(let ((parent (make-array n))
(rank (make-array n :initial-element 0)))
(dotimes (i n) (setf (aref parent i) i))
(list parent rank)))
(defun uf-find (uf x)
"パス圧縮付き find。経路上の全ノードを根に直結する。"
(let ((parent (first uf)))
(when (/= (aref parent x) x)
(setf (aref parent x) (uf-find uf (aref parent x))))
(aref parent x)))
(defun uf-union (uf x y)
"ランクによるマージ。木の高さを低く保つ。"
(let* ((rx (uf-find uf x))
(ry (uf-find uf y))
(parent (first uf))
(rank (second uf)))
(unless (= rx ry)
(cond ((< (aref rank rx) (aref rank ry)) (setf (aref parent rx) ry))
((> (aref rank rx) (aref rank ry)) (setf (aref parent ry) rx))
(t (setf (aref parent ry) rx) (incf (aref rank rx)))))
uf))
(defun count-components-uf (n edges)
(let ((uf (make-uf n)))
(dolist (edge edges)
(uf-union uf (first edge) (second edge)))
(loop for i from 0 below n
count (= i (uf-find uf i)))))Code language: Lisp (lisp)パス圧縮とランクによるマージを組み合わせた Union-Find の find と union は実用上ほぼ O(1) です。
Union-Find は「辺を順次追加しながら連結判定する」オンライン処理に向いており、DFS とは補完関係にあります。
16. 問題42 最短経路（BFS・ダイクストラ）
隣接リスト graph、始点 start、終点 end-node を受け取り、始点から終点までの最短辺数（重みなし）または最短距離（重みあり）を返す関数を書いてください。
重みなし BFS の例:
graph[0] = (1 2)、graph[1] = (3)、graph[2] = (3)、graph[3] = ()
(bfs-shortest graph 0 3) → 2 ← 0→1→3 または 0→2→3
重みあり ダイクストラの例:
graph[0] = ((1 . 4) (2 . 1))
graph[1] = ((3 . 1))
graph[2] = ((1 . 2) (3 . 5))
graph[3] = ()
(dijkstra 4 graph 0) → #(0 3 1 4)
0→0=0, 0→2=1, 0→2→1=3, 0→2→1→3=4
到達不能な場合は most-positive-fixnum を返す。Code language: PHP (php)BFS は重みなしグラフに、ダイクストラは正の重みのグラフに使います。
優先度キューの品質が性能の鍵になります。
16.1. BFS 最短路 — O(V + E)
(defun bfs-shortest (graph start end-node)
(let ((dist (make-array (length graph) :initial-element nil)))
(setf (aref dist start) 0)
(let ((queue (list start)))
(loop while queue do
(let ((v (pop queue)))
(when (= v end-node)
(return-from bfs-shortest (aref dist end-node)))
(dolist (neighbor (aref graph v))
(when (null (aref dist neighbor))
(setf (aref dist neighbor) (1+ (aref dist v)))
(setf queue (nconc queue (list neighbor)))))))
nil)))Code language: Lisp (lisp)16.2. ダイクストラ法 — O((V + E) log V)
(defun dijkstra (n weighted-graph start)
"weighted-graph[v] = ((neighbor . weight) ...)"
(let ((dist (make-array n :initial-element most-positive-fixnum))
(pq (list (cons 0 start))))
(setf (aref dist start) 0)
(loop while pq do
(let* ((entry (pop pq))
(d (car entry))
(v (cdr entry)))
(when (<= d (aref dist v))
(dolist (edge (aref weighted-graph v))
(let* ((neighbor (car edge))
(weight (cdr edge))
(new-dist (+ d weight)))
(when (< new-dist (aref dist neighbor))
(setf (aref dist neighbor) new-dist)
;; 実用では cl-heap ライブラリの priority-queue を使う。
;; sort は O(|pq| log |pq|) なので本番では非推奨。
(setf pq (sort (cons (cons new-dist neighbor) pq)
#'< :key #'car))))))))
dist))Code language: Lisp (lisp)重みなしなら BFS、重みが正ならダイクストラを使います。
優先度キューの品質が性能の鍵です。cl-heap ライブラリを使えば sort が不要になります。