Atcoder Grand Contest 006 D. Median Pyramid Hard

Atcoder Grand Contest 006 D. Median Pyramid Hard

D: Median Pyramid Hard - AtCoder Grand Contest 006 | AtCoder

感想

いいところまでは考えられたような気がしたけど結局解説を読んで。
てきとうに書いて投げたら通った。
最近は二分探索をあまりバグらせない気がする。

解法

頂上が$\ x\ $以上であるかどうかで二分探索する。すべての数を、$\ x\ $以上であるかどうかによって1と0のみで分類でき、各マスは下の3マスの多数決になることから、パターンを見出す。

実装

#include "bits/stdc++.h"
using namespace std;

int main() {
        int n;
        scanf("%d", &n);
        int N = 2 * n - 1;
        vector<int> a(N);
        for (int i = 0; i < N; i ++) scanf("%d", &a[i]);
        int lb = 1, ub = N;
        while (ub - lb > 1) {
                int mid = (lb + ub) / 2;
                vector<int> b(N);
                for (int i = 0; i < N; i ++) b[i] = a[i] >= mid;
                int m = N / 2;
                if (b[m] == b[m + 1] || b[m] == b[m - 1]) {
                        (b[m] ? lb : ub) = mid;
                } else {
                        int left = m, right = m;
                        while (left > 0 && (b[left] ^ b[left - 1]) == 1) left --;
                        while (right < N && (b[right] ^ b[right + 1]) == 1) right ++;
                        if (m - left < right - m) (b[left] ? lb : ub) = mid;
                        else (b[right] ? lb : ub) = mid;
                }
        }
        printf("%d\n", lb);
        return 0;
}