東京大学プログラミングコンテスト2013 D - 壊れかけのヒープ

問題

utpc2013.contest.atcoder.jp

解法

N <= 100 と制約が結構ゆるいので, 「m <= 1000 くらいまでヒープの大きさを試して, 配列の大きさが m で valid になるなら m を返す」みたいな感じでやれば OK です。valid になるかどうかの判定は, 「まだ配列に入っていない数のうち, 入れることが出来る数値」を後ろから貪欲に入れていけば良いです。

const int INF = 1e9+7;

bool ok(const vector<int>& A, int m) {
    int n = A.size();
    set<int> S;
    vector<int> B(m+1, INF);
    for (int i = 0; i < n; i++) {
        B[m-n+i] = A[i];
        S.insert(A[i]);
    }
    for (int i = m-1; i >= 1; i--) {
        int tar = 0;
        int ptr = (i-1)/2;
        if (i%2) {
            tar = min(B[i], B[i+1]) - 1;
        } else {
            tar = min(B[i], B[i-1]) - 1;
        }
        if (B[ptr] < INF) {
            if (B[ptr] > tar) return false;
            continue;
        }
        while (tar >= 0) {
            if (S.find(tar) == S.end()) break;
            tar--;
        }
        if (tar < 0) return false;
        S.insert(tar);
        B[ptr] = tar;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = N; i < 1000; i++) {
        if (ok(A, i)) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}