SRM646 div1 250

問題

n個の整数numbersが与えられる。
各数字を1回につき、1ずつ増やしたり減らしたりできる。
少なくともk個の連続した整数がある状態を作るための最小回数を求める。

-10^7 <= numbers[i] <=10^7, distinct
n<=47
k<=|numbers|

考え方

与えられた数字から、ある整数集合z,z+1,z+2,...を作ることを考える。
まず、最小回数であることを考えると、ソートしておいて連続したk個でz,z+1,z+2,...を考えても問題ない。

最適化したい目的関数を考えると、
f(z) := |numbers[i] - z| + |numbers[i+1] - (z+1)| + ... + |numbers[i+k-1] - (z+k-1)|
になり、最小となるzを求めることになる。

どんな形になっているか？を考えて、最適なzを求める。

a-z	では、v字型の関数になる。最適なzはz=aのとき。
a-z	+	b-z	では、下に凸な多角形のような関数になる。最適なzは、z=aまたはz=b、または、f(z)がz軸と平行となる区間でのz、になっている。

ただし、z軸と平行な区間は、aまたはbを含むので、z=aまたはz=bも最適解となっている。

同様に、f(z)はΣ|a-z|でいうところのz=aの時に最適解になりうるので、それをすべて調べればよい。