AtCoder Grand Contest 006: D - Median Pyramid Hard

,

http://agc006.contest.atcoder.jp/tasks/agc006_d

多くの部分で定数倍高速化$O(N^2)$を試みたが、最良でも$5$倍足りずでだめだった。

solution

答えに関して二分探索。 答え$a_k \ge L$だとすると、$b_i = (a_i \ge L) \in \{ 0, 1 \}$だとして同様に作ったピラミッドの頂点も$1$であるはず。 $0, 1$なら答えは$O(N)$で求められる。 $n - 1 \equiv 0 \pmod{2}$にしておいて$2$回ずつmedianを取るように考えると楽。 全体で$O(N \log N)$。

implementation

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

int median(int a, int b, int c) {
    if (a > b) swap(a, b);
    return max(a, min(b, c));
}

template <typename UnaryPredicate>
int binsearch(int l, int r, UnaryPredicate p) { // [l, r), p is monotone
    assert (l < r);
    -- l;
    while (r - l > 1) {
        int m = (l + r) / 2;
        (p(m) ? r : l) = m;
    }
    return r; // = min { x in [l, r) | p(x) }, or r
}

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> a(2 * n - 1);
    repeat (x, 2 * n - 1) {
        scanf("%d", &a[x]);
    }
    // solve
    if ((n - 1) % 2 == 1) {
        vector<int> b(2 * n - 3);
        repeat (x, 2 * n - 3) {
            b[x] = median(a[x], a[x + 1], a[x + 2]);
        }
        a.swap(b);
        -- n;
    }
    int result = binsearch(1, 2 * n, [&](int limit) {
        vector<char> b(2 * n - 1);
        repeat (x, 2 * n - 1) {
            b[x] = a[x] > limit;
        }
        int result = b[n - 1];
        int dist = 2 * n;
        repeat (x, (2 * n - 1) - 2) {
            if ((b[x] != b[x + 1] and b[x + 1] == b[x + 2])
                    or (b[x] == b[x + 1] and b[x + 1] != b[x + 2])) {
                int ndist = abs((x + 1) - (n - 1));
                if (ndist < dist) {
                    dist = ndist;
                    result = b[x + 1];
                }
            }
        }
        return not result;
    });
    // output
    printf("%d\n", result);
    return 0;
}