SRM 518 div1 med:ConvexSequence

SRM518の練習会に参加しました。easyとmed通せました。わーい。

easyは簡単だと思うので省略します。

問題

TopCoder Statistics - Problem Statement

解法

貪欲っぽい感じで解きました。

a[i]とa[i+1]の差をb[i]とします。

凸になるためには,bの配列が単調増加になっていることが必要十分です。
こうなるための最小操作回数を求めれば良いことになりました。

で,じゃあどうやるかってことになるんですが,例えばbが
1,1,0,2,2
だったとしましょう。

a[0]を1下げるという操作はb[0]を1下げてb[1]を1上げるという操作に相当します。よって,まず2,3個目の1,0を解決するためには
1,0,1,2,2
とするやり方と
1,1,1,1,1
とするやり方があります。

このときどっちを選ぶのが良いのか考えます。bは単調増加数列にしなければならないので,bの最初のほうの数字が小さくなる方が有利です。よって,前者のように2個目を下げて3個目を上げるやり方が最適です。

こんな感じでやると答えを求めることが出来ます。

class ConvexSequence {
public:
    long long getMinimum(vector <int> a) {
        int n = a.size();
        if (n <= 2) return 0ll;
        ll ans = 0;
        vector<ll> b(n-1);
        for (int i = 0; i < n-1; i++) b[i] = a[i+1]-a[i];
        while (1) {
            bool update = false;
            for (int i = 0; i < n-2; i++) {
                if (b[i] > b[i+1]) {
                    update = true;
                    ll ch = (b[i]-b[i+1]+1) / 2;
                    ans += ch;
                    b[i] -= ch;
                    b[i+1] += ch;
                }
            }
            if (!update) break;
        }
        return ans;
    }
};