3060

格子点上の点がいくつか与えられ、幅Dで格子をその上に書くとき、通過する最小の点数を答えよ、という問題。

法Dで考えれば良くて、x軸方向の分布、y軸方向の分布、x軸とy軸の両方を決めた時の分布、というものをそれぞれの点の座標から計算しておく。後は一番小さくなるようにx軸とy軸を決定すれば良い。無駄な計算をしないようにメモリをふんだんに使いましょう、系の問題。