kmjp's blog

競技プログラミング参加記です

TopCoder SRM 832 : Div1 Medium SparseOnes

うーん、考え方はあってるのに本番しょうもないミスで落とした。
https://community.topcoder.com/stat?c=problem_statement&pm=17671

問題

01で構成される文字列Sを、以下のように定める。
非負整数のうち、二進数表記したときに1が連続する箇所がないようなものを小さい順に考える。
それぞれ二進数表記したものを連結してSとする。

正整数A,Bが与えられるので、SのうちA文字目以上B文字目未満の位置において1の登場回数を求めよ。

解法

f(n) := Sのprefix n文字中における1の登場回数
とすると、解はf(B-1)-f(A-1)である。
あとはf(n)を求めよう。

以下を考える。
cnt(k) := 二進数表記でk桁になるようなLeading Zeroを含まない正整数のうち、1が連続する箇所がないものの総数
sum(k) := cnt(k)が該当する整数の二進数表記における1の登場回数

これは最上位から二番目の1の登場箇所を総当たりすることを考えれば、容易にDPで求めることができる。
また、kを70程度まで考えるとk*cnt(k)の総和がBの上限を超えるので、そこまで考えればよい。

あとはこれらをもとにf(n)を求めよう。
S[n]がちょうどk桁の整数の二進数表記である場合、sum(1)+sum(2)+....+sum(k-1)の分はf(n)に計上される。
あとは、k桁の整数の二進数表記のうち、桁数の総数がnを超えない範囲でカウントしていこう。
その際、再帰的に上の桁から1がどこにあるかを求めて行こう。

ll pat[100];
ll sum[100];
int N;

class SparseOnes {
	public:
	int hoge2(ll v) {
		ll ov=v;
		ll val=0;
		ll id=0;
		v--;
		int i,j;
		for(i=1;i<=N;i++) {
			if(v>=i*pat[i]) {
				v-=i*pat[i];
			}
			else {
				id=v%i;
				val=1LL<<(i-1);
				int la=i-1;
				v/=i;
				v++;
				while(v) {
					v--;
					if(v==0) break;
					for(j=0;j<la-1;j++) {
						if(v<=pat[j+1]) {
							val|=1LL<<j;
							la=j;
							break;
						}
						v-=pat[j+1];
					}
				}
				break;
			}
		}
		int cnt=0;
		int ret=0;
		for(i=60;i>=0;i--) {
			if(val&(1LL<<i)) cnt=1;
			if(cnt) {
				if(id==0) {
					ret=(val>>i)&1;
					break;
				}
				id--;
			}
		}
		
		return ret;
	}
	ll hoge(ll v) {
		if(v<=0) return 0;
		ll ov=v;
		
		ll ret=0;
		int i,j;
		for(i=1;i<=N&&v;i++) {
			if(v>=i*pat[i]) {
				ret+=sum[i];
				v-=i*pat[i];
			}
			else {
				ll num=v/i;
				ll lef=v%i;
				if(lef) {
					int add=i-lef;
					num++;
					for(j=1;j<=add;j++) ret-=hoge2(ov+j);
				}
				ll cur=1LL<<(i-1);
				int la=i-1;
				int bit=1;
				while(num) {
					num--;
					ret+=bit;
					if(num==0) break;
					for(j=0;j<la-1;j++) {
						if(num<=pat[j+1]) {
							cur|=1LL<<j;
							la=j;
							bit++;
							break;
						}
						else {
							ret+=sum[j+1]+bit*pat[j+1];
							num-=pat[j+1];
						}
					}
				}
				break;
			}
		}
		return ret;
	}
	long long count(long long A, long long B) {
		ZERO(pat);
		ZERO(sum);
		pat[1]=sum[1]=1;
		int i,j;
		for(i=2;i<=99;i++) {
			pat[i]=1;
			sum[i]=1;
			for(j=1;j<=i-2;j++) {
				pat[i]+=pat[j];
				sum[i]+=sum[j]+pat[j];
			}
			if(pat[i]>=1LL<<50) {
				N=i;
				break;
			}
		}
		return hoge(B-1)-hoge(A-1);
	}
}

まとめ

やることはすぐ思いついたけど、正確な実装に割と手間取った。