TopCoder SRM 659 Div1 Easy ApplesAndOrangesEasy

最近Div1 Easyを難しくしたものがDiv2 Hardに出るパターンを見かけるな。
http://community.topcoder.com/stat?c=problem_statement&pm=13791

問題

N個の果物(リンゴかオレンジ)を順に買ったとする。

果物を購入している過程で、常に
「直前に買ったmin(K,購入済み数)個の果物のうち、リンゴはK/2個以下である」
ということがわかっている。
また、N個のうち幾つかリンゴを買ったことが確定している箇所が与えられる。

条件を満たす果物の購入順のうち、リンゴの購入可能な最大数を求めよ。

解法

購入順に購入物を確定させていく。
A[i]をi番目の購入物とし、0ならオレンジ、1ならリンゴとする。

i番目にリンゴを買ったと仮定する。
sum(A[i-K+1], ... , A[i])==K/2+1 の場合、直前K個に(K/2+1)個のリンゴが含まれるので、どこかリンゴをあきらめなければならない。

その場合、できるだけ後ろの購入順のリンゴをあきらめた方がよい。
なぜなら、A[x]の影響はA[x+K-1]を購入するときまで及ぶので、xが大きい箇所をあきらめた方が、以後より多くのケースで直前K個のリンゴ購入数減少効果が得られる。

よって、A[i-K+1], ... , A[i]のうち、A[x]=1でありかつリンゴ購入が確定してない最大のxを求め、そこをオレンジにすればよい。

int must[2020];
int did[2020];

class ApplesAndOrangesEasy {
	public:
	int maximumApples(int N, int K, vector <int> info) {
		ZERO(did);
		ZERO(must);
		FORR(r,info) must[r-1]=1;
		
		if(K<=1) return 0;
		
		int i,x,y;
		FOR(i,N) {
			did[i]=1;
			if(count(did+max(i+1-K,0),did+i+1,1)>K/2) {
				for(x=i;x>=max(0,i-(K-1));x--) if(did[x] && must[x]==0) {
					did[x]=0;
					break;
				}
			}
		}
		return count(did,did+N,1);
	}
}

まとめ

Div2 Hardよりはだいぶ簡単。