解説

分割統治法（Divide and Conquer）は、大きな問題を複数の小さな独立した部分問題に分割し、それぞれを独立に解いた後、結果を統合して元の問題の解を得るアルゴリズム設計手法です。「分割（Divide）→統治/征服（Conquer）→結合（Combine）」の3ステップが基本構造です。代表例はマージソート（配列を半分ずつ分割して再帰的にソート後マージ）、クイックソート、二分探索、FFTなどです。選択肢cの「全体を幾つかの小さな問題に分割して、それぞれを独立に処理した結果をつなぎ合わせる」が分割統治法の正確な説明です。

なぜ他の選択肢は違うのか

選択肢 ア

「粗い解を逐次改良して精度を上げる」は近似法・逐次改善法（ヒルクライミングなど）の説明です。分割統治法は近似ではなく正確な解を求め、逐次改良ではなく分割・統合を行います。

選択肢 イ

「全ての組み合わせを調べ無駄なものを除く」は枝刈り（Branch and Bound）や後退法（バックトラッキング）の説明です。組み合わせの削減を目的とする手法であり、分割統治法とは異なります。

選択肢 エ

「各時点で最良の解を選択し繰り返す」は貪欲法（Greedy Algorithm）の説明です。局所最適を積み重ねて全体の解を得ようとする手法で、分割統治法とは設計思想が異なります。

解くときのポイント

アルゴリズム設計手法4種の区別：分割統治法＝「独立分割→各解決→結合」、動的計画法＝「重複部分問題をメモ化」、貪欲法＝「各ステップで局所最適」、バックトラッキング＝「全探索＋枝刈り」。マージソートが分割統治法の典型例。