SRM518 Div1 500

とぷこだ 過去問

問題

整数値の配列aが与えられる。
配列x[0..N-1]が
　1<=i<=N-2で、x[i-1]+x[i+1]>=2*x[i]
を満たす場合、convexである、という。
与えられた配列aに対し、次の操作ができる。
　・iを一つ選び、そのa[i]を1引く
配列がconvexになるまでにかかる最小の操作回数を求める。

考え方

要素が10^9と大きいが、満たすべき値がどの程度になるか？がわかれば1ずつ引く必要はないので、greedyで間に合ってしまう。(が、証明は難しい)

greedyは、問題文をそのままやるだけで、
　・iを見て、convex条件を満たしていなければ、a[i]を条件を満たせる(a[i-1]+a[i+1])/2に減らす
　・変化がなくなるまでこれを繰り返す
　・減らした差分をすべて合わせると答えになる
で求められる。

引きすぎる可能性は、(a[i-1]+a[i+1])/2が満たすべき最小の動き(差分)をするので、ない。

考え方2

貪欲法だと、{0,10^9,0}で48回程度なので、時間がかからなそうなことがわかる。(感覚では)
でも、計算量を見積れる別な方法がある。


convex条件を書き換えると、
　x[i] >= 2*x[i-1] - x[i-2]
と書ける。
すると、i-1まで確定しているとして、iの下限が与えらえる。

各iについて、x[i]の値を求めていきたい。
x[i]の下限と上限(＝a[i])が与えられているので、二分探索で求められる。
条件を満たせるか否かは、a[i]を決めたとして、i+1〜N-2で(書き換えたconvex条件を使って)convexな配列を作れるか判定する。

{6,5,1,5,3,3}の場合、i=1の5を変更するとすると、i=2以降で満たせるかどうか判定する。
i=2の1は、2*5-6=4より小さいので、条件を満たせない、ので、5は満たせない。
二分探索でこの数値を求めていけば、条件を満たせる配列が求められる。

これだと、なめるのと二分探索と判定でO(n^2*log m)になる？

反省

  • 雰囲気、線形計画法なので、単体法を使うのかなと思った
    • どっちにしろ計算量がみつもれない、、、
  • 実験してみるとそれほど時間がかかっていない(SystemTestでも1msぐらいしかかかってない)
    • 実験大事