D: Equal Cut - AtCoder Regular Contest 100

BとCの間区切りを総当たりで固定する。

このとき、前半部分と後半部分の両方ともできるだけ均等に分けるのが最適。なぜか。

AとBの区切りを考えてみよう。AとBをできるだけ均等に（差が最小になるように）分けたときの小さい値をlow, 大きい値をhighとする。また、AとBをそれ以外の分け方にしたときの小さい値をLOW, 大きい値をHIGHとおく。A, Bの値同士の関係について言えば、均等に分けたほうがいいのはわかりやすい( $high - low \lt HIGH - LOW$ のため)。

分かりづらいのは、A, Bの値に対するC, Dの関係のほう。 $LOW \lt low \leq high \lt HIGH$ より、LOW, low, high, HIGHは以下の図のような座標を取るはず。 f:id:parukii:20180702142502j:plain どこにC, またはDの点をプロットしても、(A, B)の(C, D)に対する関係で言えば、最大値-最小値は(low, high)の組を使ったほうが小さいか等しいことがわかる。

CとDの区切りについても同様。

これで前半も後半もできるだけ均等に分けたほうがいいことがわかった。BとCの間の区切りを小さいほうから見ていくことを考えると、内側の区切りは前と同じかそれよりも右側にずれるかのいずれか。なので尺取り法が使える