分割統治法とは（全体像）
分割統治法は、そのままでは大きすぎる問題を、小さな部分問題に分けて解き、最後に結果を合わせる設計の考え方。「分けて、片づけて、まとめる」と覚えるとよい。
身近な例が答案の採点。1000枚の答案を10人で分けて配り（分割）、各自が担当ぶんを採点し（統治）、最後に点数を集計する（結合）。一人で全部やるより、分けたほうがずっと速い。これが分割統治法のイメージだ。
ポイントは、分けた部分問題が互いに独立して解けること。お互いの結果を待たずに別々に解けるからこそ、分けるうまみが出る。
詳しく：3ステップと代表例だけ覚えれば戦える
ここが記事の心臓部。分割統治法は、次の3つの手順で進む。
分割統治法の3ステップ
| ステップ | 英語 | やること |
|---|---|---|
| ①分割 | Divide | 問題を小さな部分問題に分ける |
| ②統治 | Conquer | 各部分問題をそれぞれ解く（小さければそのまま） |
| ③結合 | Combine | 部分の解を合わせて全体の答えにする |
この考え方を使った代表的なアルゴリズムが、試験でよく問われる。
分割統治法の代表例
| アルゴリズム | 分け方 | 速さの目安 |
|---|---|---|
| マージソート | 半分ずつに分けて、整列して合わせる | O(n log n) |
| クイックソート | 基準値で大小に分ける | O(n log n)（平均） |
| 2分探索 | 真ん中で半分にしぼる | O(log n) |
たとえばマージソートは、配列を半分ずつに分け続け、小さくなったら整列し、合わせながら戻していく。分割統治の流れがそのまま形になった代表例だ。
つまり、分割統治法は「大きい問題を半分などに分け、解いて、合わせる」やり方。分けることで、まとめて解くより速くなる、というわけだね。
なお、各部分を解くときに自分自身と同じやり方をくり返す（再帰）ことが多い。再帰は「実現する手段」で、分割統治は「設計の方針」という関係だ。
わかりやすく言い換えると
要するに、分割統治法は「分けて・片づけて・まとめる」だ。
①分割 … 大きな問題を小さく分ける（答案を10人に配る）
②統治 … 分けた部分をそれぞれ解く（各自が採点する）
③結合 … 結果を合わせて答えにする（点数を集計する）
代表例は「マージソート・クイックソート・2分探索」。この3つをセットで覚えると、問題で見分けやすくなる。
試験のツボ
🔴 一番出る：分割・統治・結合の3ステップ
①分割（小さな部分問題に分ける）
②統治（各部分を解く）→ ③結合（合わせて答えにする）
🔴 次に出る：代表例
①マージソート・クイックソートはO(n log n)
②2分探索はO(log n)
🟡 押さえると安定：再帰との関係
①再帰は「実現する手段」
②分割統治は「設計の方針」で、両者は別の話
よくある間違い
①「分割統治法と再帰はまったく同じもの」→ ✗ 再帰は実現する手段、分割統治は設計の方針。同じではない。
②「分割統治法はどんな問題にも使える」→ ✗ 部分問題に分けられ、解を合わせられる問題でこそ効く。
③「マージソートは分割統治法ではない」→ ✗ マージソートは分割統治法の代表例。半分に分けて整列し合わせる。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（3ステップ）
分割統治法の手順に関する次の記述のうち、正しいものはどれか。
- 問題を分けずに、最初から全体をひとかたまりのまま一気に解くのが分割統治法だ
- 問題を小さな部分に分割し、各部分を解いてから、解を結合して全体の答えにする
- 問題を分割した後は、部分問題をいっさい解かずに、そのまま結合するだけの手順だ
- 問題を結合してから分割し、最後に統治する順番で進めるのが正しい手順とされる
解答は 2 だよ。
分割統治法は①分割→②統治（各部分を解く）→③結合の順なんだ。「分けて・片づけて・まとめる」で覚えてね。
選択肢1の「分けない」、選択肢3の「解かずに結合」、選択肢4の「結合してから分割」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 小さく分けてから解く |
| 2 | ✓ | 分割→統治→結合の順 |
| 3 | ✗ | 各部分をきちんと解く |
| 4 | ✗ | 分割が先、結合が最後 |
オリジナル問題2（代表例）
分割統治法を使った代表的なアルゴリズムに関する次の記述のうち、正しいものはどれか。
- マージソートは分割統治法とは無関係で、配列を分けることもいっさいしないものだ
- 2分探索は分割統治法ではなく、先頭から順に1つずつ調べていくだけの方法である
- 分割統治法の代表例は、マージソート・クイックソート・2分探索などが挙げられる
- 分割統治法の代表例はバブルソートだけで、ほかには一つも存在しないものとされる
解答は 3 だよ。
分割統治法の代表例はマージソート・クイックソート・2分探索なんだ。どれも「半分などに分けて解く」のが共通点だよ。
選択肢1の「マージソートは無関係」、選択肢2の「2分探索は順に調べる」、選択肢4の「バブルソートだけ」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | マージソートは代表例 |
| 2 | ✗ | 2分探索も分割統治 |
| 3 | ✓ | マージ・クイック・2分探索 |
| 4 | ✗ | 代表例は複数ある |
オリジナル問題3（再帰との関係）
分割統治法と再帰の関係に関する次の記述のうち、正しいものはどれか。
- 再帰は実現する手段、分割統治は設計の方針であり、両者は別のことを指している
- 再帰と分割統治はまったく同じ言葉で、どちらも同じものを指しているにすぎない
- 分割統治法は再帰をいっさい使わず、ループだけで実現すると決められた手法だ
- 再帰は設計の方針、分割統治は実現する手段という関係で、両者の役割は逆だ
解答は 1 だよ。
再帰は実現する手段、分割統治は設計の方針なんだ。分割統治は再帰で実現されることが多いけど、同じ言葉ではないよ。
選択肢2の「同じ言葉」、選択肢3の「再帰を使わない」、選択肢4の「役割が逆」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 再帰＝手段・分割統治＝方針 |
| 2 | ✗ | 同じ言葉ではない |
| 3 | ✗ | 再帰で実現することが多い |
| 4 | ✗ | 手段と方針が逆 |
まとめ
押さえどころ
- 🔴 3ステップ ＝ 分割（分ける）→統治（解く）→結合（合わせる）。
- 🔴 代表例 ＝ マージソート・クイックソート（O(n log n)）、2分探索（O(log n)）。
- 🟡 再帰との関係 ＝ 再帰は実現する手段、分割統治は設計の方針。別の話として区別する。
次に学ぶ
- 再帰 ── 分割統治を実現する代表的な手段。自分自身を呼び出すしくみを押さえると分割統治が腑に落ちる。
- 動的計画法DP ── 同じく問題を小さく分ける手法。部分問題が重なるときに使う点が分割統治との違い。
執筆: SikakuQuest編集部