IndiaHacks 2016 - Online Edition C. Bear and Up-Down

問題

codeforces.com

解法

条件が合わない場所がたくさんありすぎると, どうスワップしても条件が合わない場所すべてに対応することが出来ないので, NG です。ということで, 条件が合わない場所が 10 箇所より多い場合は問答無用で 0 を出力しましょう(多分 4 箇所より多いとダメなはずだけど念の為)。

で, 条件に合わない場所が少ない場合は, スワップには必ず 条件に合わない場所を絡ませないといけないことを考えて, 全探索しましょう。下のコードでは,

• 条件に合わない場所 - その他 のスワップ
• 条件に合わない場所 - 条件に合わない場所 のスワップ

の 2 通りに分けています。

bool check(const vector<int>& t, int index) {
    int n = t.size();
    if (index%2 == 0) {
        if (index > 0) if (t[index] >= t[index-1]) return false;
        if (index < n-1) if (t[index] >= t[index+1]) return false;
    } else {
        if (t[index] <= t[index-1]) return false;
        if (index < n-1) if (t[index] <= t[index+1]) return false;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];
    vector<int> ng;
    for (int i = 0; i < n-1; i++) {
        if (i%2 == 0) {
            if (t[i] >= t[i+1]) ng.emplace_back(i);
        } else {
            if (t[i] <= t[i+1]) ng.emplace_back(i);
        }
    }
    for (int i = 1; i < n; i++) {
        if (i%2 == 0) {
            if (t[i] >= t[i-1]) ng.emplace_back(i);
        } else {
            if (t[i] <= t[i-1]) ng.emplace_back(i);
        }
    }
    sort(ng.begin(), ng.end());
    ng.erase(unique(ng.begin(), ng.end()), ng.end());
    ll ans = 0;
    if (ng.size() > 10 || ng.size() == 0) {
        cout << 0 << endl;
    } else {
        auto ok = [&](int a, int b) {
            if (!check(t, a)) return false;
            if (!check(t, b)) return false;
            for (int p : ng) {
                if (!check(t, p)) return false;
            }
            return true;
        };
        auto out = [&](int a) {
            for (auto p : ng) if (a==p) return false;
            return true;
        };
        for (int i = 0; i < n; i++) {
            if (out(i)) {
                for (auto p : ng) {
                    swap(t[p], t[i]);
                    if (ok(p, i)) ans++;
                    swap(t[p], t[i]);
                }
            }
        }
        int size = ng.size();
        for (int i = 0; i < size; i++) for (int j = i+1; j < size; j++) {
            swap(t[ng[i]], t[ng[j]]);
            if (ok(ng[i], ng[j])) ans++;
            swap(t[ng[i]], t[ng[j]]);
        }
        cout << ans << endl;
    }
    return 0;
}