TopCoder SRM 659 Div2 Hard ApplesAndOrangesHard

変わった形で制限を変えている。
http://community.topcoder.com/stat?c=problem_statement&pm=13780

問題

問題設定はDiv1 Easyと同じである。
ただしN,Kの上限が大きく、一方リンゴ購入の確定箇所が少ない。

解法

基本的な考え方はDiv1 Easyと同じ。
ただしDiv1 Easyの解法はO(NK)なので、今回は適用できない。
TopCoder SRM 659 Div1 Easy ApplesAndOrangesEasy - kmjp's blog

一方リンゴ購入の確定箇所が少ないことに注目する。
Nが大きく、リンゴ購入の確定箇所が少ないということは、リンゴ購入未確定の箇所がほとんどを占めることになる。
また、リンゴ購入が未確定の場合、リンゴ購入のパターンはK個ずつ周期性を持つことがわかる。

よって、リンゴ購入が確定している位置の周辺だけはDiv1 Easy同様に貪欲にA[i]を求めていき、未確定の区間が2*K以上連続している箇所は周期性を用いてまとめて処理できる。

Div1 EasyではA[i]をすべて配列に格納したが、今回はNが大きいためA[i-(K-1)]..A[i]のうち1となる添え字をdequeで管理するようにした。
以下のコードではcheck関数がA[cur-(K-1)]..A[cur]が条件を満たすか判定する箇所である。

以下はO(K*|info|*log(|info|))である。

class ApplesAndOrangesHard {
	public:
	deque<int> D;
	set<int> I;
	int K, ret;
	
	void check(int cur) {
		
		if(D.size() && D[0]==cur-K) D.pop_front();
		D.push_back(cur);
		ret++;
		
		if(D.size()>K/2) {
			for(int x=D.size()-1;x>=0;x--) if(I.count(D[x])==0) {
				D.erase(D.begin()+x);
				break;
			}
			ret--;
		}
	}
	
	int maximumApples(int N, int K, vector <int> info) {
		
		if(K<=1) return 0;
		
		this->K=K;
		D.clear();
		I.clear();
		
		FORR(r,info) I.insert(r-1);
		I.insert(N);
		ret = 0;
		
		int cur=0, x;
		FORR(r,I) {
			
			if(r-cur>2*K+1) {
				FOR(x,K) check(cur++);
				
				int sl= (r-cur-1)/K;
				ret += sl * D.size();
				cur += sl * K;
				FOR(x,D.size()) D.push_back(D[0]+K*sl),D.pop_front();
			}
			
			for(;cur<=r && cur<N;cur++) check(cur);
		}
		
		return ret;
	}
}

まとめ

最初dequeでなくsetを使ってA[i]=1となるiをカウントしたがTLEした。