久々に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); } };
まとめ
今回は割と簡単に解けた。