読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

SRM659 div.1 250 ApplesAndOrangesEasy

問題

SRM659 div.1 250 ApplesAndOrangesEasy
各要素がリンゴかミカンである、要素数がNの列を考える。ここで、[i, i+K-1]の区間で列に含まれるリンゴの数を \lfloor K/2 \rfloor個以下に制限することとする。列において、要素が必ずリンゴであるインデックスの情報infoが与えられるので、制限を満たす列でリンゴは最大何個列に含まれうるか?

制約

 2 \le K \le N \le 2000

解法

リンゴを複数の場所に置くことができる場合、おける場所のうち先頭以外においても意味が無いことがわかる。
よって、各iについて、[i-K+1, i], [i-K+2, i+1], ..., [i, i+K-1]の各区間において、その時点でリンゴが何個含まれるか計算し、その最大値が \lfloor K/2 \rfloorより小さいならば、リンゴをおけばよい。

計算量

[i-K+1, i], [i-K+2, i+1], ..., [i, i+K-1]の各区間においてリンゴが何個含まれるかは、愚直に計算すると O(K^2)であるが、尺取法のように計算するとO(K)で求めることができる。
よって、O(NK)

コード