用語の定義

蟻本

プログラミングコンテストチャレンジブック
競技プログラミング界隈でのバイブル的な本
競プロ参戦にあたって必要なベーシックな知識が網羅的に掲載されている

Fence Repair

POJ 3253
北京大学のオンラインジャッジの3253番の問題
一般化するとハフマン符号の問題らしい
蟻本の49ページから解説が掲載されている

貪欲法を使うという問題ですが、なぜそれが貪欲的になるのかがスッと理解できなかったので、検証しようというのが発端です。

問題文

農夫ジョンは、フェンスを修理するため、とても長い板から$N$個の板を切り出そうとしています。切り出そうとしている板の長さは$ L_1,L_2,\dots ,L_N$であり、元の板の長さはちょうどこれの合計になっています。板を切断する際には、その板の長さの分だけのコストがかかります。例えば、長さ$21$の板から$5,8,8$の$3$つの板を切り出したいとします。長さ$21$の板を長さ$13$と$8$の板に切断すると、コストが$21$かかります。その$13$の板をさらに$5$と$8$の板に切断すると、コストが$13$かかります。合計で$34$のコストがかかります。最小で、どれだけのコストで全ての板を切り出すことができるでしょうか。

制約

$1\leqq N\leqq 20000$
$1\leqq L_i\leqq 20000$

多くの問題では、木であったり、そうでなくともある種のグラフ構造に一般化できることが多いです。
今回の問題文で示されている例を二分木で表すと以下のようになります。

各切断時のコストは親ノードの値となるので、総コストは葉でないノードの値を全て足した値です。
上の例では葉でないノード（白色）の総和が、$13+21=34$で問題文の総コストと一致します。

このときの総コストを最小にするというのが題意です。

解答の方針

蟻本の解説方針

与えられた板のうち、短い順に$2$枚を取り除き、代わりにマージした長さの板を加える。
マージした板の長さの和をコストに加算し、最後の1枚になるまで再帰させる。
その際に得られるコストが最小になっている。

読むとなんとなく正しそうな気はするものの、本当にそうかがパッと納得できませんでした。
トップダウンで解いていくと条件分けがエグいのでボトムアップで考えるという発想の転換を伝えることが主旨だとは思いますが、のちのちにもっと難しい問題が解説されたときにここを理解していないと詰みそうに感じたので、追求することにします。

固定条件と変動要素

何が固定（前提）で、変動はどんな操作によって生じるかを見ることがあらゆる問題を解く上での基本的な方針です。
今回は貪欲法の章で紹介されている問題なので、必ず総コストが小さくなる操作があるということはメタ的にわかります。
実際に解く場面においては、その判断も含めてアルゴリズムを選定していく必要があります。

さて、本問では切断完了時の全ての板の長さが与えられるので、最終的に葉となるノードの数は確定しています。
すなわち、どのような順序で葉を組み合わせていくかで、木構造が変化します。

変動要素の検証

変化のしかたを捉えるといっても、いきなり複雑なケースで考えても失敗します。
かの偉大な数学者であるデカルトも「困難は分割せよ」と言いました。

めちゃくちゃ単純なケースに分割して考えていくというのが、あらゆる問題を解く上で重要なスキームです。
では、最も単純なケースはなんでしょう？一緒に考えていきましょう。

N=1のケース

言うまでもなく$N=1$のケースが最も単純です。つまり、元の板のままで切断することはありません。
これだと変動もクソもなくて、コストは常に$0$です。$N$を増やしていきましょう。

N=2のケース

これは切断回数が$1$となるケースです。これも、切断後の板の長さが確定している時点でバリエーションはありません。
さらに$N$を増やしましょう。

N=3のケース

お待たせしました。$N=3$からようやくバリエーションが出てきます。
まずは簡単のために、$3$枚ある切断後の板の長さを$A\leqq B \leqq C$というように置いてみます。
これは一般性を失わない仮定でしょう。

さて、ここでの切り方は$3$パターン考えられます。

$(A+B+C) \rightarrow (A+B),C \rightarrow A,B,C$
$(A+B+C) \rightarrow A,(B+C) \rightarrow A,B,C$
$(A+B+C) \rightarrow B,(C+A) \rightarrow A,B,C$

ちょっと文字で書いても分かりにくいので、面倒ですが図を作りました。

総コストに影響するのは、図の赤色部分の違いだけです。そのほかの部分は位置こそ違えど和の値は変わりません。
つまり、このケースにおいて総コストを最小にすることは$(A+B),(B+C),(C+A)$の中から最小を選ぶという問題と同値です。

バリエーションが十分かを丁寧に見ると、$3$つの中から$2$つ選ぶ、つまり${}_3 \mathrm{C} _2 = {}_3 \mathrm{C} _1 = 3$で、たしかに$3$パターンしかあり得ません。
では、どのパターンが最小かといえば、当然ながら値が小さい方から$2$つ選んだ$(A+B)$になります。

まとめると、$N=3$であれば小さい方から$2$つ選んで切り出せばよいということになります。
この事実を用いて、$N=4$のケースも考えてみましょう。

N=4のケース

$N=3$では、総コストが最小になるパターンを1通りに絞ることが出来ました。
メタ的に考えれば、貪欲法なのでこれ以降は漸化式的な感じでパターンを絞っていけるということになりそうです。

さて、$N=4$のケースは板が$4$枚です。
最初の切断でケース分けをすると、板$ABCD$を$1+3$枚で切り分けるか、$2+2$枚で切り分けるかでパターンが分かれます。

1+3枚のパターン

$1+3$枚で切り分けるパターンは、$N=3$のケースを根側に拡張した形です。最初に$1$回切ったあとは$N=3$と同じ形になり、板$ABC$が$\{ABC,ABD,ACD,BCD\}$のいずれかに変わるだけです。

つまり、全部で$4\times 3=12$パターンあるものの、実質は最初にどれを切り分けるかの$4$パターンに帰着します。
ここで、$N=3$のケースの総コストを一般化すると、$2A+2B+C$です。
（$3$つの中から小さいものを$2$つ選ぶのと、最も大きいものを選ぶことは同じ）

これに対して、$A\leqq B \leqq C \leqq D$となる$D$を追加すると、$N=4$のケースになります。
総コストを整理すると以下の$4$パターンです。

$3A+3B+2C+D$：最初に$D$を切る
$3A+3B+2D+C$：最初に$C$を切る
$3A+3C+2D+B$：最初に$B$を切る
$3B+3C+2D+A$：最初に$A$を切る

さて、ここでいったん止めておいて$2+2$枚のパターンを見てみましょう。

2+2枚のパターン

少し考えると、どんな組み合わせで切り分けても総コストは$2\times(A+B+C+D)$になることが分かります。

まとめて比較する

ここまでの場合分けにより、$N=4$のケースとして今考えなくてはならないパターンは先ほどの$4$パターンと合わせて、全部で$5$つに絞られることがわかりました。

では、ここで$5$つの大小関係を比較するために、$2\times(A+B+C+D)$を全てのケースから引いてみましょう。

$;;;;;;0;;;;;;$：最初に$2+2$枚に切り分ける
$A+B-D$：最初に$D$を切る
$A+B-C$：最初に$C$を切る
$A+C-B$：最初に$B$を切る
$B+C-A$：最初に$A$を切る

この中で最小のコストとなり得る値は、どれになるでしょうか。
$A\leqq B \leqq C \leqq D$を考えると以下が分かります。

$;;;;;;0;;;;;;$：$A+B-D$が正の値の場合に最小
$A+B-D$：負となるケースで最小
$A+B-C$：負になり得るが、より大きな数$D$を引く$1$つ上のパターンの方が小さいので候補とならない
$A+C-B \geqq 0$：大小関係より必ず$0$以上なので候補とならない
$B+C-A \geqq 0$：大小関係より必ず$0$以上なので候補とならない

すなわち、$A+B\leqq D$の判定結果によって最小のケースが変わるということになります。

蟻本の解説に立ち返る

$A+B\leqq D$をよく見てみましょう。
これって要するに$A+B$のマージ結果を加えて再度ソートしているのと同じことですよね。

なぜならば、$C\leqq D$である時点で、いずれのケースでも$C$は最大値にはなり得ないためです。$３$つの中の小さい方から$2$つ選ぶことは、最大を$1$つ選ぶのと同値になります。しからば最大になり得ない$C$の情報は不要です。

これを図でもう少し分かりやすく可視化していきましょう。
$N=4$のケースにおいて、最小側から$2$つ選んでマージした$A+B$を$M$とした問題を考えます。

先ほど示した通り、ケースは以下の$2$通りしかありません。
$M$が最大のケース、あるいは$D$が最大のケースです。

そうなんです。結局トップダウンでいろいろこねくり回しても、最も小さい方からマージして置換していくと$N=4$のケースが$N=3$のケースに帰着するんです。確認のためにあらためて$M$に$A+B$を戻すと、以下のように先ほどまでトップダウンで議論していた場合分けの形にちゃんとなります。

ボトムアップで捉え直す

さて、ここで各葉についてかかるコストを見てみましょう。
すると葉$1$枚が総コストに占める値は、その葉ノードの値と深さの積であることはすぐに分かります。ためしに先ほどの図の葉$A$を根まで辿ってみてください。根に至るまでの$1$本道全てに$A$が含まれており、かつ他のルートには$A$が含まれていないことが分かります。

そして、値と深さという$2$軸を同時に考えるのは難しいので、同じ深さという観点で考えます。どういう木構造になるかは未知だったとしても、同じ深さにおいてはより値が小さい方がコストを小さくします。ということは、最も深い方から順に葉を埋めていくことを考えると、常に最小のペアで埋めていくことが貪欲的になります。なぜなら、重ねてになりますが“同じ深さなら値が小さい方がコストが小さくなる”からです。

これをトップダウンでやろうとすると、深さ$1$の時点で複数選択を取らなければならず、いきなり場合分けが発生します。$N=4$で十分面倒なことはご理解いただけたかと思いますので、最大ケースの$N=20000$など実質無理だということになります。

得られた教訓

困難は分割する
逆の方向からできないか試してみる
複数軸ある場合は、いずれかの軸を固定して考えてみる

実際の解答コードはプログラミングコンテストチャレンジブックを参照してください。

##余談
競プロは$2020$年の$8$月に入ってからはじめました。
普段は個人ブログに記事を投稿しています。