典型攻略：絶対値の和の最小化 - ロアちゃんかわいい

おはようございます。　明日から夏休みですね。

DP記事とか言うのは知りません。（もうちょっとかかりそうです）

ここまで解いた問題で2回使うことになった内容なので知識として記録しときます。

TeX記法とかいうので表示する練習も兼ねています。上手く表示されない場合はご一報ください～。

実数列 $a_{i}(1≦i≦n)$ に対して
$\sum_{i=1}^{n}|a_{i} - x|$
というxの関数を考えます。
この式をf(x)と置くと、y=f(x)は折れ線のグラフを書きます。
絶対値の和なので $f(x) ≧0$ は明らかですが、これはxをどこまでも小さく、あるいは大きくしていくと、無限大に発散することがわかります。
この関数の最小値を与えるxを考えます。

さて、最小値を求めるにはどうしたらよいでしょうか？
結論から言うと、xが $a_{i}$ の中央値になる時にf(x)は最小になります。
例えば数直線で級数の各項はxと $a_{i}$ の距離なので、xの右に $a_{i}$ がn個ある時にxを右に1動かしたらf(x)の値はn減ることがわかります。
それぞれの点にxが1だけ近づくので。

xが右にΔx動くとすると、右にn個 $a{i}$ があればf(x)は当然nΔx減ります。
xの左にm個 $a_{i}$ があるなら、右にxを1動かすとf(x)はm"増え"ます。
なのでxの左と右にある $a_{i}$ の個数が等しくなる時に値が最小でーす。

勝った！第三部完！
一見当たり前だけど！こういう典型知識の積み重ねがなんかいい感じにあれするんですよ！

以下使う問題です。（なんか2017年の慶應医数学で似た問題が出てたみたいです。こういう各場合にxをちょっとずらして考えていくみたいな発想は受験生諸氏も覚えておくといいかもしれません）

C - Linear Approximation

B - AtCoder Market

ではおやすみなさい～。