n-knuu's logs

憧れ駆動。だいたい競プロ

Codeforces Round #210 Div.2 D / Div.1 B - Levko and Array

練習会に参加して1完だった。

問題

Codeforces Round #210 Div.1 B - Levko and Array
素数nの数列aが与えられる。数列のうちk個まで値を変更して、 \max |a_{i+1} - a_{i}|を最小にするとき、その値を求めよ。

制約


1 \le k \le n \le 2000 \\
 -10^9 \le a_{i} \le 10^9

解法

二分探索で解を求める。
ここで、問題を「あるxを決めて、数列の各要素を点(i, a[i])と見なしてn-k個以上の点を選んで折れ線を引いたときに、各折れ線の傾きがx以下となるような折れ線を作れるか?」と言い換えて、以下のdpを考える。
dp[i] := (i番目の点を使って折れ線を作ったときに、その傾きをx以下にできる場合の、使える点の個数の最大値) とすると
dp[i] = max(1, max{dp[j] + 1 | j < i かつ i番目の点とj番目の点の傾きがx以下})
ここで、あるi(1からN)でN-dp[i] >= Kならば、上で述べたような折れ線を作ることができる。(選ばれなかった点は値を変更してよい点なので、傾きx以下の直線にそって適当な点を選ぶことができる。)

計算量

 O(N^2 \log\max(a))

コード


感想

  • 数列を2次元平面上の点とみて、直線の性質を調べる、みたいなアイデアは前にも見た気がするのに思い浮かばなかった
    • SRM647 div2 hardがそんな問題だった(数列xとtが与えられて、点(x[i], t[i])を考えれば傾きが...みたいな問題)