Break PGC [Kodamanと愉快な仲間たち H]

https://www.hackerrank.com/contests/kodamanwithothers/challenges/break-pgc

前提知識

• 二分探索

解説

https://www.hackerrank.com/contests/kodamanwithothers/challenges/break-pgc/submissions/code/1316477241

問題文に最大値は最小でいくつになりますか？と質問がある。 競技プログラミングでの典型テクとして「最大値の最小は二分探索で解く」というものがある。 今回も例に漏れず、これで解ける。

かけることのできる力で二分探索を行う。 check(ma) := かけることのできる力の最大値がmaのときに、全て壊すことができるか これは貪欲に壊せる所から順に壊していって、全て壊すことができればtrueで良い。 だが、O(NlogINFlogN)するとTLEした。 queueとかを使って、O(NlogINF)くらいにしておこう。

int N, X, A[101010];
bool broken[101010], ok[101010];
//---------------------------------------------------------------------------------------------------
int get(int i) {
    int a = A[i];
    if (broken[i - 1]) a -= X;
    if (broken[i + 1]) a -= X;
    return a;
}
//---------------------------------------------------------------------------------------------------
bool check(int ma) {
    rep(i, 1, N + 1) broken[i] = false;
    broken[0] = broken[N + 1] = true;
    rep(i, 1, N + 1) ok[i] = false;

    queue<int> que;
    rep(i, 1, N + 1) if (get(i) <= ma) {
        que.push(i);
        ok[i] = true;
    }
    while(!que.empty()) {
        int i = que.front();
        que.pop();

        broken[i] = true;

        if (!broken[i - 1] and !ok[i - 1] and get(i - 1) <= ma) {
            ok[i - 1] = true;
            que.push(i - 1);
        }

        if (!broken[i + 1] and !ok[i + 1] and get(i + 1) <= ma) {
            ok[i + 1] = true;
            que.push(i + 1);
        }
    }

    int cnt = 0;
    rep(i, 1, N + 1) if (ok[i]) cnt++;
    return cnt == N;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;
    rep(i, 1, N + 1) cin >> A[i];

    int ng = 0, ok = inf;
    while(ng + 1 != ok) {
        int md = (ng + ok) / 2;
        if (check(md))
            ok = md;
        else
            ng = md;
    }
    cout << ok << endl;
}