きままにものづくり

日々の気付いたことなんかを書いてます。

SRM659Div1Easy

問題

N個のフルーツが並んでおり、それらはりんごかオレンジである。K個の連続するフルーツは最大でもK/2個のりんごしかない。
いくつかのりんごの位置の配列が与えられた時の最大のりんごの数を求めよ。

解法

左側の要素から探索していき、周囲K個のりんごの数がK/2より小さいならその要素をりんごにする。

計算量

O(NK^2)

コード