hotpepsiの練習帳

SRM 659

21:31

https://competitiveprogramming.info/topcoder/srm/round/16462/div/1

Div1 Easy (250) ApplesAndOrangesEasy

問題

• N個のりんごまたはみかんがあり、1つずつ順番に全て食べる
• 連続してK個食べたうちの、りんごはK/2個以下である
• りんごを食べた情報である配列infoが与えられる
• info[i]番目に食べたのはりんごである
• りんごを食べられる最大数を求める

方針

• 適当な貪欲
• Failed System Test
• 位置iのK個の和を求めておく
• 位置iについて、i-K+1からiまで全ての場所のK個の和がK/2個未満なら、位置iをりんごにすることができる
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_659/ApplesAndOrangesEasy.cpp

結果

x-- 0pt 199th/293 rating 1350 -> 1303 (-47)

単純に最後のK個の範囲内にN/2個未満なら置く、にしてしまった。

http://togetter.com/li/820832