Codeforces Round #210 (Div. 1) B. Levko and Array

問題

codeforces.com

解法

c(a) の値について二分探索します。c(a) <= x が成り立つかどうかを判定する関数を考えます。

dp[i] = (i 番目の要素を固定するとして, i 番目以下の数のうち値を変更しなければならない要素の数の最小値) とします。
これがわかると, (dp[i]+(n-i-1)) の最小値が K 以下なら c(a) <= x が成り立つことがわかります。dp[N-1] <= K なら OK, というわけではないことに注意しましょう(これで 1WA した)。例えば 数列の 0 にすべての数字を合わせれば x = 0 と出来るのに, 配列 a の最後の要素が 1 だったりすると, dp[N-1] >= 1 となるとかで作れます。

あとは dp[i] をどう計算するかですが, i 番目の要素の直前に固定する要素が j であるとすると, j と i に挟まれた要素の数 i-j-1 個は値を変更することになるので, dp[i] = min(dp[j]+(i-j-1)) となります。

ただ, j として何でも選んで良いというわけではありません。|a[i]-a[j]| <= x*(i-j) だったら 固定する要素として j を選んで良いです。これが成り立っていれば, j と i に挟まれた要素は適当にすることで隣り合った要素間の差を x 以下に出来ます。

const int MAXN = 2222;
int N, K;
ll a[MAXN];
int dp[MAXN];

bool ok(ll x) {
    for (int i = 0; i < N; i++) {
        dp[i] = i;
        for (int j = 0; j < i; j++) {
            if (abs(a[i]-a[j]) <= x*(i-j)) {
                dp[i] = min(dp[i], (i-j-1) + dp[j]);
            }
        }
    }
    int mini = N;
    for (int i = 0; i < N; i++) {
        mini = min(mini, dp[i]+(N-i-1));
    }
    return mini <= K;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> a[i];
    ll low = -1, high = 2e9;
    while (high - low > 1) {
        ll med = (high+low)/2;
        if (ok(med)) high = med;
        else low = med;
    }
    cout << high << endl;
    return 0;
}