B. Motarack's Birthday (Codeforces Round #619 Div. 2)

問題

https://codeforces.com/contest/1301/problem/B

問題概要

いくつかの項が不明の数列がある。不明の場所全てに同じ数字を入れるとするとき、隣接する項の差の絶対値の最大値が最小になるようにするには、何をいれればよいか？また、その時の絶対値の最大値はいくつか？

考察

不明な項に隣接している不明でない項の最大値と最小値を取って、その中間を取れば最大値が最小化できます。中間より大きくすれば最小値との差の絶対値が増加してしまいますし、小さくすれば最大値との差の絶対値が増加してしまいます。

ただし、注意しなければならない点がいくつかあります。

• すべての項が不明の場合は挿入する値は何でもよくて、すべての項が同じ値になるので差は0になるということ
• （おそらく実装上問題になることはないと思いますが）不明な項が3つ以上並んでいる場合は、間に挟まれている項は考慮する必要がまったくないこと
• 不明でない項が3つ以上並んでいる場合は、間に挟まれている項は不明な項と接してないので、挿入する値の算出には影響しないこと
• 不明でない項が2つ以上並んでいる場合は、それらの差も絶対値の最大値の候補になること
  • clarでも言及されていた、サンプルの2番目がそのケースに当てはまりますね

実装、ちょっと汚くなってしまいました。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000001;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        int mx = 0;
        int l = INF;
        int r = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == -1) continue;
            bool bl = false;
            if (i != 0) {
                if (a[i - 1] == -1) {
                    bl = true;
                } else {
                    mx = max(mx, abs(a[i] - a[i - 1]));
                }
            }
            bool br = false;
            if (i != n - 1) {
                if (a[i + 1] == -1) {
                    br = true;
                } else {
                    mx = max(mx, abs(a[i] - a[i + 1]));
                }
            }
            if (bl || br) {
                l = min(l, a[i]);
                r = max(r, a[i]);
            }
        }
        if (l == INF && r == 0) {
            cout << "0 0" << endl;
            continue;
        }
        int ans = max(mx, (r - l + 1) / 2);
        cout << ans << " " << max(r - ans, ans - l) << endl;
    }
}

自分用おぼえがき

最初、最大値の最小を求める問題なので二分法か？と思ったのですが、計算で求められることに気づけたのでそうしました。

もっとも、タグにはbinary searchがついているようです。しかしこれ、二分法でどうやって解くんでしょう？