TopCoder SRM 514 Div2 Hard MagicalGirlLevelThreeDivTwo

久々にDiv2 Hardの練習を再開。
http://community.topcoder.com/stat?c=problem_statement&pm=11479

問題

K要素の01から構成される文字列配列first[i]から、以下の要領で配列A[i]を生成する。

• i
• i>=Kなら、A[i]=A[i-1] + A[i-K-1] + A[i-2K-1] + ..

ここで数n,lo,hiが与えられるので、A[n][lo..hi]に含まれる1の数を数えよ。

解法

A[n][0..hi]中の1の数からA[n][0..(lo-1)]の1の数を引けばよいので、結局xに対してA[n][0..x]を求めればよい。
Aの各要素はフィボナッチ数列の要領で文字数が増えるため、文字列そのものを格納するのは容量的に無理である。
そこでAの各要素の長さと1の数だけ事前に計算しておく。

A[n]=A[n-1]+A[n-K-1]+A[n-2K-1]+... より、A[n][0..x]=A[n-1]+A[n-K-1]+A[n-2K-1]+...+(A[n-pK-1]の一部)となるようなpが登場するはずである。
A[n-1]～A[n-(p-1)K-1]までの1の数は事前に計算した値で求められるので、後は再帰的にA[n-pK-1]の一部に含まれる1の数を計算すればよい。

int K;
ll len[101];
ll nb[101];

class MagicalGirlLevelThreeDivTwo {
	public:
	vector <string> f;
	
	ll okok(int id,ll val) {
		if(val<=0) return 0;
		if(id<K) return count(f[id].begin(),f[id].begin()+val,'1');
		ll ret=0;
		for(id=id-1;id>=0;id-=K) {
			if(val >= len[id]) ret+=nb[id], val -=len[id];
			else return ret + okok(id,val);
		}
		return ret;
	}
	
	int theCount(vector <string> first, int n, long long lo, long long hi) {
		int i,j;
		f=first;
		K=first.size();
		ZERO(len);
		ZERO(nb);
		
		FOR(i,K) len[i]=first[i].size(),nb[i]=count(first[i].begin(),first[i].end(),'1');
		
		for(i=K;i<=n;i++) {
			j=i-1;
			len[i]=0;
			while(j>=0) {
				len[i]+=len[j];
				nb[i]+=nb[j];
				j-=K;
				len[i]=min(len[i],10000000000000000LL);
				nb[i]=min(nb[i],10000000000000000LL);
			}
		}
		return okok(n,hi+1)-okok(n,lo);
	}
};

まとめ

今回は割と簡単に解けた。