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個まで値を変更して、を最小にするとき、その値を求めよ。
制約
解法
二分探索で解を求める。
ここで、問題を「ある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以下の直線にそって適当な点を選ぶことができる。)
計算量
コード
感想
- 数列を2次元平面上の点とみて、直線の性質を調べる、みたいなアイデアは前にも見た気がするのに思い浮かばなかった
- SRM647 div2 hardがそんな問題だった(数列xとtが与えられて、点(x[i], t[i])を考えれば傾きが...みたいな問題)