- greedy解がなぜうまくいくのか分からなかったので考えてみた
- 「(x, ?) から (x+width, ?+y) に行く時に比べて (x+width, ?+y+1) に行く時ではどれだけ長くなるか」を各 x, y について求めておく
- 上記は、x が固定なら y が大きいほど大きい
>>> import math
>>> [ math.hypot(3,y+1)-math.hypot(3, y) for y in range(10) ]
[0.16227766016837952, 0.4432736152956096, 0.6370894116552956, 0.7573593128807152, 0.8309518948453007, 0.8772520376540687, 0.9075691733645392, 0.9282306394536217, 0.9428292351876078, 0.9534735284054126]
- この数列の 0〜Y の和は、「(x, ?) から (x+width, ?) に行く時に比べて (x+width, ?+Y) に行く時ではどれだけ長くなるか」なので、
- x → x+width と移動するときに、同時に Y 個上に移動するときの増加コストと同じ
- この数列の小さい方から Y 個の和は、0〜Y の和と等しい (ポイント)
- なので、全部の差分をソートして小さい方から length 個足せば、全部で length 個上にいくときの最小増加分がわかる
