貪欲法を丁寧に証明してみた　 CODE THANKS FESTIVAL 2017(Parallel) C問題編

貪欲法の証明は難しいことが多い。（学科のレポート課題で死んだトラウマ）

こういうときは問題を解いた後丁寧に証明を書くことで、理解が深まるらしい。そこで、AtCoderで貪欲法の問題を解いたらたまに証明をなるべく丁寧に書いて載せてみようと思う。

今回の問題

概要：機械が$N$台あり、$i$番目の機械は初め$a_i$秒でプレゼントを1個作れる。ただし1個作るごとに、（1個作るのに必要な時間が）$b_i$秒ずつ増えてしまう。違う機械を同時に使うことはできない。

どの機械をいつ使うかをうまく選んで、$K$個のプレゼントをできるだけ早く作りたい。$K$個のプレゼントを作るためにかかる最小の時間は何秒か？

答えの方針

直感的には、プレゼントを1個作るごとに「いま一番速い機械」を選べばよさそうである。つまり、プレゼントを$t$個作った後の機械$i$の速度（プレゼント1個を作るのに必要な秒数）を$a_i^t$として、$a_i^t$が最小となる$i$を$i+1$回目の機械に選べばよい。

証明

$t ~(1 \leq t \leq K)~$回目に選ばれる機械の番号を並べた列を$x_1 \cdots x_K$とする。さらに、$a_i(=a_i^0)$が最小である$i$を$i^*$とする。

「問題の最適解（$K$個作るのにかかる時間が最小となるような列）で、$x_1=i^*$であるようなものが存在する（★）」ことを示す。

もしも（★）が示せれば、2回目に選ぶ機械についても、$a_i^1$が最小になるものを選ぶような最適解が存在することを同様に示せる。これを$K$回繰り返せば証明が終わる。

（★）の証明：

もしも$x_1=i^*$となる最適解が存在しないと仮定する。適当な最適解$x_1 \cdots x_K$を一つ取る。ここで、$x_1 \cdots x_K$を適当に並び替えても、最終的にかかる時間が変わらないことに注目すれば、（各機械が選ばれた回数のみによって最終的な時間が決定することは容易にわかる）$x_t = i^*$となる$t$は存在しないことがわかる。

そこで、この最適解$x_1 \cdots x_K$の$x_1 \neq i^*$を$i^*$に置き換える。すると、もちろん1個目のプレゼントを作るのにかかる時間は減少し、2個目以降のプレゼントを作るのにかかる時間も、$x_2$以降に$i^*$は現れない（つまり劣化の影響を受けない）ので増加することはない。（むしろ、$i^*$に置き換える前の$x_1$が1回目で劣化しなくなるので、速くなる可能性がある）。したがって、$x_1 \neq i^*$を$i^*$に置き換えた列$i^* \cdots x_K$もまた最適解である。これは最初の仮定に矛盾するので、背理法により（★）が示された。■

感想

貪欲法の証明の定石は「貪欲でないところを貪欲なものに入れ替えても悪化しない」ことを示すことである（らしい）。ただし毎度（個人的に）発生する問題は、入れ替えによって後の方に影響が出ることをどう処理するかが難しいところである。

たとえば今回の例では、$x_1 \neq i^*$を$i^*$に置き換えた場合に、$x_2$以降に$i^*$が含まれていると、それが劣化の影響を受けて遅くなるため、一概に「悪化しない」とは言えない。この可能性をあらかじめ封じるために、入れ替えで不変であることに着目した。

こういうのを頭の中でぱっと思いついて実装できる人はすごいと思う。

（おまけ）実装

Submission #24057249 - CODE THANKS FESTIVAL 2017(Parallel)

プライオリティキューを用いた。まずプライオリティキューに組$(a_i,b_i)$を全部入れて初期化し、$t~(1\leq t \leq K)$回目の操作では、$a_i$が最小となる組を取り出し、$a_i$に$b_i$を加算して挿入する。初期化が$O(N)$,取り出しや挿入に$O(logN)$かかるので、結局$O(N)+O(KlogN)$かかる。これは、制約のもとで間に合う。