【SRM659Div1】ApplesAndOrangesEasy【250point】

問題概要

$N$個の果物(リンゴかオレンジ)を食べる. リンゴの方が好きなのでリンゴをなるべく多く食べたい.

だが, 食べる順序を考えたとき, 全ての連続する$K$個の果物の中で, リンゴは半分未満でなければならない(※).

$info_i$番目($1\leq i\leq |info|$)には必ずリンゴを食べなければならないとき, 食べられるリンゴの数の最大値を求めよ.

制約

$2 \leq K \leq N \leq 2000$
$0 \leq |info| \leq N$
$1 \leq info_i \leq N$ ($1\leq i\leq |info|$)
$info$の各要素は互いに異なり, (※)に反することはない

考察

単純に左から貪欲すれば良さそう(証明略).

各$i$について, リンゴを食べると仮定したとき, それを含む全ての長さ$K$の区間で(※)に反しなければリンゴを食べてよい.

既にリンゴを食べることがわかっているなら$1$, そうでないなら$0$を要素として持つ BIT を持てば, 1 回の判定が$O(\log N)$でできるので全体で$O(N^2 \log N)$.

提出コード(C++🔆)

struct ApplesAndOrangesEasy {
    int N;
    int K;
    vector<int> info;
    int maximumApples(int _N, int _K, vector<int> _info) {
        N = _N, K = _K, info = _info;
        BinaryIndexedTree<int> bit(N);
        for (auto& e: info) bit.add(--e, 1);
        REP(i, N) {
            if (bit.sum(i, i + 1)) continue;
            bool valid = true;
            REP(j, N - K + 1) {
                int k = j + K - 1;  // [j, k]
                if (i < j or k < i) continue;
                int apple = bit.sum(j, j + K) + 1;
                if (apple > K / 2) {
                    valid = false;
                    break;
                }
            }
            if (valid) bit.add(i, 1);
        }
        return bit.sum(N - 1);
    }
};