問題概要
$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);
}
};