AtCoder 茶～緑向け：貪欲法の合法性を証明するための実践的ガイド

はじめに

「貪欲法で解けることを証明したか」という問いに自信を持って答えるのは、実際に問題を解くよりも難易度が高いです。少なくとも、現時点で茶～緑ランクの私には難しく感じます。
なぜ貪欲法の証明が必要で、具体的に何を押さえれば「証明した」と言えるのでしょうか？
本記事では、貪欲法に対する”直観”を”最低限の論理”に変換する力を身につけること、実装前に自信を持つためのチェックリストを獲得することを目標とし、ABC431 C 問題を例に「競プロにおける証明の立て方」を考察します。

貪欲法の証明はなぜ難しいのか

前提として、なぜ貪欲法の証明が必要なのでしょうか。それは貪欲法が「局所的に最善の選択をする」という手法であり、このアルゴリズムが「全体で最善の選択になるか」が保証されないからです。
読んでくださっている皆さんにも「なんとなくいけそう」という思考で提出して WA を食らったり、提出を躊躇して時間を取られたりした経験があるかもしれません。自信を持って証明ができないと、本番のスコアに影響してしまいます。
正しさの裏付けができなかったり、自信を失ってしまったりするのは「証明のパターン」を知らないのが原因かもしれません。

貪欲法の証明のパターン

貪欲法の証明は多様に見えますが、実際には以下に示す 3 つのパターンのいずれか（またはその組み合わせ）でほとんど説明できます。
以下の章で、それぞれのパターンについて証明手順を示します。

まずは全パターンに共通する点を挙げておきます。
本記事では「与えられた選択肢から 1 つを選ぶことを順に繰り返したときの選び方」を解と呼ぶこととします。
いずれのパターンにせよ、まずは貪欲法によってどんな解 $G$ が構成されるか書き起こす必要があります。
問題によって

• 解が存在するかを問われていれば「貪欲法によって解 $G$ が得られる ⇒ 解が存在する」こと
• 最適解が求められているなら「最適解が $X$ である ⇒ 解 $G$ が最適解 $X$ に含まれる」こと

をそれぞれ証明すればよいです。

各証明パターンは数学的に重なる部分がありますが、問題によって適したアプローチを選べると楽に証明できます。

交換論法：順番を変えても損をしない

昇順や降順に選ぶのが最適であると主張したいとき、

• 昇順/降順から逆転している箇所を交換したとき、全体のスコア（目的関数）が悪くならないこと

を示すことで、任意の最適解 $O$ をソート順に処理する方法 $G$ に置き換えられることを証明します。

1. 最適解 $O$ の中に貪欲法 $G$ の順序と逆転する箇所があると仮定する。
2. その部分を $G$ と交換した解 $O'$ を作る。
3. この交換が
   • ほかの要素の選択を妨げることがなく
   • 全体のスコアを悪くしないこと
     を示す。このとき、解 $O'$ も最適解である。
4. 逆転がなくなるまでこれを繰り返すことにより、最終的に $O$ を $G$ と同じ順序に変形できる。

要素の順序だけが重要な問題で使いやすいパターンです。

追い越し不能：常に有利な状況を保てる

目先の利益を常に最大化すれば全体を最大化できると主張したいとき、

• 貪欲に $i$ 個選んだ状態とほかの選び方とを比べたとき、前者のほうが「後に続く選択肢が広い」状態にあるか

を示すことで、貪欲な選択 $G$ が常にほかの最適解 $X$ と同等か有利である（選択の幅が広い）ことを示します。

1. 任意の解 $X$ と貪欲な選択 $G$ を比べて、初めの $i - 1$ 回の選択をした後に残りの選択肢が等しいか、または $G$ のほうが広いと仮定する。
2. $i$ 回目の選択において、貪欲な選択をしても残りの選択肢が狭まらない（単調性が保たれる）ことを示す。
3. 数学的帰納法より、$G$ は常にほかの解よりも不利にならず、結果として最適解の 1 つである。

区間スケジュール問題などで使いやすいパターンです。

縮小法：一部を決めても全体最適が崩れない

部分問題において貪欲な選択が最適であり、これを繰り返して全体の最適解が得られると主張したいとき、

• 先頭で貪欲な選択を行った後の残りの問題が「サイズが小さくなっただけの同じ問題」となること

を示すことで、貪欲な選択 $G$ が全体の最適解を導くことを示します。

1. 最初の選択として、貪欲に最善の要素を選ぶ。
2. この選択によって最適解に到達できなくなることがないことを示す。
   • すなわち、最適解のうち少なくとも 1 つはこの選択を先頭に含むことを示せばよいです。
3. 最初の選択をした後、残りの部分問題が（サイズが小さい）同じ構造の問題となっていることを示す。
4. 数学的帰納法より、貪欲な選択を繰り返すことで全体の最適解 $G$ が得られる。

一般の最適化問題で、部分問題での選択が全体の問題の性質を変えないときに使えるパターンです。

実例：ペア形成問題の貪欲法による解法と証明

以下では ABC 431 C - Robot Factory を例に、直観的な理解と「縮小法」を用いた証明手順を示します。

問題の概要

• 数列 $H$ および $B$ が与えられる。数列 $H$ の長さは $N$ で、数列 $B$ の長さは $M$ である。
• 数列 $H, B$ の要素 $H_i,\ B_i$ を取り出して $H_i \le B_i$ となるようなペア $(H_i, B_i)$ を $K$ 個作りたい。
• 与えられた $K \le min(N, M)$ について、実際に $K$ 個のペアを作れるか否かを答えよ。
• ただし複数のペアで 1 つの要素を共有してはならない。

直観的な理解

ペアを 1 つ作る際、「数列 $H$ の大きな要素」と「数列 $B$ の小さな要素」は $H_i \le B_i$ の条件を満たしづらいことが直観的に理解できます。この直観から以下の性質が見いだせます。

• ペアを作る際に数列 $H$ の小さな要素を選ぶほど、相手に選べる $B$ の要素の候補が増える
• 逆に数列 $H$ の大きな要素を選ぶほど、相手に選べる $B$ の要素の候補が減る

この直観から、貪欲法が使えそうだと考えられます。

実装

まず、貪欲法による $K$ 個のペアの作り方 $G$ を考えてみます。

• 数列 $H$ を昇順 $(h_1,\ \dots,\ h_N)$ に並べ、小さいほうから $K$ 個を取り出して数列 $H' = (h_1, ..., h_K)$ を作る。
  • $H$ の側はできるだけ前の要素に小さい値を割り当てたいので、最小の $K$ 個を選んでいます。
• 数列 $B$ を昇順 $(b_1,\ \dots,\ b_M)$ に並べ、大きいほうから $K$ 個を取り出して数列 $B' = (b_{M - K + 1},\ \dots,\ b_M)$ を作る。
  • $B$ の側はできるだけ後ろの要素に大きい値を割り当てたいので、最大の $K$ 個を選んでいます。
• ペア $(h_1, b_{M - K + i})$ を作る（以下、簡単のため $(H'_i, B'_i)$ と表す）。
• もし 1 組でも $H'_i > B'_i$ となる場合、$K$ 個のペアは作れない。
• 各ペアについて $H'_i \le B'_i$ が成り立つならば $K$ 個のペアを作れる。

上記の解法を python で実装した部分コードを示します。

H.sort()
B.sort()

Hd = H[:K]
Bd = B[-K:]

for i in range(K):
    if not (Hd[i] <= Bd[i]):
        ans = "No"
        break
else:
    ans = "Yes"

縮小法による証明

ここでは「縮小法：一部を決めても全体最適が崩れない」パターンに則って貪欲法による解が最適であることを示します。

証明したいこと

ここで証明したいのは以下の事柄です。

• 必要条件：$K$ 個のペアを作れる $\implies$ すべての $1 \le i \le K$ に対して $H'_i \le B'_i$ が成り立つ
• 十分条件：$K$ 個のペアを作れる $\impliedby$ すべての $1 \le i \le K$ に対して $H'_i \le B'_i$ が成り立つ

十分条件については、もしすべての $i$ で $H'_i \le B'_i$ が成り立つなら、その対応でペアを作れば重複なく $K$ 個のペアが作れます。こちらは明らかです。
よって、以下で必要条件のほうを証明します。

0. 証明のための準備

証明の前準備として、次の補題が成り立つことを示します。

• $H$ から任意に $K$ 個を取って昇順に並べた数列を $S = (s_1 \le \cdots \le s_K)$ とする。
• これと $H$ から小さい順に $K$ 個を取り出した数列 $H'$ について以下のことが成り立つ。
  • $1 \le i \le K$ に対して $h_i \le s_i$
• 同様に、$B$ から任意に $K$ 個を取って昇順に並べた数列を $T = (t_1 \le \cdots \le t_K)$ とする。
• これと $B$ から大きい順に $K$ 個を取り出して昇順に並べた数列 $B'$ について以下のことが成り立つ。
  • $1 \le i \le K$ に対して $t_i \le b_{M - K + i}$

$H'$ は $H$ の最小 $K$ 個であり、$S$ は任意の $K$ 個の昇順列なので、昇順列同士を比較すると必ず $h_i \le s_i$ となります。$B$ 側についても同様に成り立ちます。

1. 最初に貪欲な最善手を取る

1. 先ほど定義した $S,\ T$ で $K$ 個のペアが作れると仮定します。ここで $s_1$ は $S$ の中で最小の要素です。
2. 一方で全体の集合 $H$ の最小の要素を $h_1$ とすると、明らかに $h_1 \le s_1$ が成り立ちます。

2. 選択によって最適解に到達できなくなることがない

1. $h_1 \le s_1 \le t_1$ が成り立つため、ペア $(h_1, t_1)$ は制約を満たします。
2. $S$ の最小要素 $s_1$ は、$H$ 全体から $S$ が選んだ $K$ 個のうち最小の要素です。一方で $h_1$ は $H$ 全体の最小値なので、$h_1$ が $S$ に含まれる場合、必ず $h_1 = s_1$ になります。
3. $s_1 \ne h_1$ の場合、$S$ に $h_1$ は含まれません。
4. よって $S,\ T$ で作った $K$ 個のペアのうち先頭を $(h_1, t_1)$ に置き換えても、残り $K - 1$ 個のペアの可否は変わりません。

3. 残りの部分問題が同じ構造の問題となっている

1. 先頭のペアを $(h_1, t_1)$ と固定すると、残りの部分問題は以下のように表せます。
   • $H \setminus \{h_1\}$、$B \setminus \{t_1\}$ から $K - 1$ 個のペアを作る。
   • ここで $H \setminus \{h_1\}$ は $H$ から $h_1$ を取り除いた集合を意味します。
2. この問題は確かに元の問題と同じ構造を持っています。

4. 同じ操作を繰り返すことで全体の最適解が得られる

1. 同様の手順で、すべてのペア $(s_i, t_i)$ を $(h_i, t_i)$ に置き換えることができます。
   $T$ は $B$ 全体から任意に選ばれた $K$ 個、$B'$ は貪欲に選んだ $B$ のうち最大の $K$ 個なので、すべての $t_i$ について $h_i \le t_i \le b_{M - K + i}$ が成り立ちます。
2. 以上より、仮定「$S,\ T$ で $K$ 個のペアが作れること」から「$i = 1,\ \dots,\ K$ について $H'_i \le B'_i$ が成り立つこと」を導くことができました。

貪欲法チェックリスト

以下のポイントをチェックすると、貪欲法が使えるかどうかを直観的に判断するのに役立ちます。

1. 後戻りは不要か？
2. 本当に有利なものから取ってよいか？
3. 交換しても損しないか？
4. 部分問題に分解できるか？

1. 後戻りは不要か？

ある時点で選んだ選択肢が将来の選択肢を消滅させたり、後が続かなくなるような悪影響を与えたりする場合、貪欲法は使えない可能性が高いです。

2. 本当に有利なものから取ってよいか？

ナップサック問題のように最大値/最小値以外の値を取ることで得するケースが考えられる場合、貪欲法は使えません。

3. 交換しても損しないか？

ある最適解を仮定したとき、その一部を貪欲な選択と入れ替えても解が悪化しないと言い切れる場合は貪欲法を使える場合があります。

4. 部分問題に分解できるか？

「1 つ選んだ後の残りの問題」が元の問題と同じ構造をしている（サイズが $N$ から $N - 1$ になっただけの同じ問題になっている）場合、貪欲法を使える可能性があります。

他の問題への応用

• 区間スケジューリング問題（終端ソート問題）
  • 終わるのが早いものを選ぶことにより残りの時間が最大化される、単調性があるパターンの代表例です。
• 辞書順最小
  • 前の文字を辞書順に小さくすることのほうが、後ろの文字の順序よりも優先される例です。
• 最小全域木（クラスカル法）
  • コストの小さい辺から採用する貪欲法が正当である有名な例です。

終わりに

解法が正しいかどうかの不安や曖昧さは「証明のパターン」と「パターンへの落とし込み方」がわかれば解消できます。
本番中の判断ではあくまで最低限の論理が押さえられていれば問題ありませんので、ぜひ復習の際には上記のパターンを活用して証明してみてください。
本記事が、貪欲法を自信を持って使えるようになるまでの一助になれば幸いです。