kmjp's blog

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

Codeforces #272 Div1 D. Dreamoon and Binary

自力で解けはしたけど若干苦戦。
http://codeforces.com/contest/477/problem/D

問題

2進数表記の数値xが与えられる。
このxを表記するため、初期値0の整数変数nを用いて以下の処理を繰り返す。

  1. nの2進数表記を、出力済みの文字列の右に追記する。leading zeroは記載不可。
  2. nをインクリメントする。

xを表記する処理順の総パターン数と、最小処理数をそれぞれ答えよ。

解法

総パターン数と最小処理数はそれぞれO(|x|^2)のDPまたはメモ化再帰で処理する。

まず総パターン数について、以下の条件でx[l,r]の次にx[r,z]を追記することができる。

  • 文字列長の制限より、z<=|x|。
  • leading zeroの条件より、x[r]==1である。
  • 後者の方が数値として大きい。
    • (r-l)==(z-r)かつx[l,r]≦x[r,z]である。
    • または(r-l)<(z-r)である。

x[l,r]がそもそもO(|x|^2)パターンあるのに、以下の2つの処理がそれぞれO(|x|)かかってしまうため、全体ではO(|x|^3)かかる。
そこで以下の2か所を工夫してO(|x|)の処理を軽減する。

  • x[l,r]を求めるのに、各zを総当たりすると遅い。
    • x[r,r+(r-l)+1], x[r,r+(r-l)+2], x[r,r+(r-l)+3], ... , x[r,|x|]の総和をまとめて求められるよう部分和を使いまわすことで、毎回総当たりすることを防ぐ。
  • x[l,r]≦x[r,z]の判定がO(|x|)かかって遅い。
    • Longest Common Substring相当の処理を行い、x[l,r]とx[r,z]の先頭一致文字数を先に列挙しておく。
    • 一致数pが(r-l)以上なら、x[l,r]==x[r,z]だし、pが(r-l)ならx[r-l+p]とx[z-r+p]を大小比較すればよい。


次に最小処理数を求める。
最後に追記する数値をx[r,|x|]とする。
その際処理回数はx[r,|x|]の値と、x[0,r]の範囲をx[r,|x|]以下の値で分割した最小分割回数の和となる。
今度は総パターン数のメモ化再帰とは逆に、文字列の右側から順にメモ化再帰して最小分割回数を求めていく。
ここでも総パターン数同様、部分列の和ならぬ部分列の最小値の保持や、O(1)の部分文字列大小判定を利用してO計算量を(|x|^2)に抑えることができる。

今回何気に|x|の上限が5000と大きいのでMLEに注意。

string S;
int L;
ll mo=1000000007;
int pat[5005][5005],pats[5005][5005];
int mi[5005][5005],mis[5005][5005];
int mat[5005][5005];
char C[5005];


void lcs(string& AA,string& BB) {
	int x,y,ma=0;
	for(x=AA.size()-1;x>=0;x--) for(y=BB.size()-1;y>=0;y--)
		mat[x][y]=(AA[x]==BB[y])?(mat[x+1][y+1]+1):0;
}
bool lessthan(int pre,int cur) {
	int l=cur-pre;
	if(mat[pre][cur]>=l) return true;
	return C[pre+mat[pre][cur]]<C[cur+mat[pre][cur]];
	
}

ll val(int cur) {
	ll v=0;
	while(cur<L) v=(2*v+(S[cur++]=='1'))%mo;
	return v;
}

ll dpdp(int pre,int cur);
ll dpdp2(int cur,int tar) {
	if(pats[cur][tar]>=0) return pats[cur][tar];
	if(tar>L) return pats[cur][tar]=0;
	pats[cur][tar]=dpdp2(cur,tar+1)+dpdp(cur,tar);
	if(pats[cur][tar]>=mo) pats[cur][tar]-=mo;
	return pats[cur][tar];
}

ll dpdp(int pre,int cur) {
	if(pat[pre][cur]!=-1) return pat[pre][cur];
	if(cur==L) return pat[pre][cur]=1;
	if(S[cur]=='0') return pat[pre][cur]=0;
	
	ll ret=0;
	int tar=cur+(cur-pre);
	if(tar<=L && pre!=cur && lessthan(pre,cur)) ret+=dpdp(cur,tar);
	ret+=dpdp2(cur,tar+1);
	return pat[pre][cur]=ret%mo;
}

int mimi(int pre,int cur);
int mimi2(int cur,int tar) {
	if(mis[cur][tar]>=0) return mis[cur][tar];
	if(cur>=tar) return mis[cur][tar]=6000;
	mis[cur][tar]=min(mimi2(cur+1,tar),mimi(cur,tar));
	return mis[cur][tar]=min(mimi2(cur+1,tar),mimi(cur,tar));
}

int mimi(int pre,int cur) {
	if(mi[pre][cur]!=-1) return mi[pre][cur];
	if(S[pre]=='0') return 6000;
	if(pre==0) return mi[pre][cur]=1;
	int& ret=mi[pre][cur]=6000;
	
	int i=cur-pre;
	if(pre-i>=0 && lessthan(pre-i,pre)) ret=min(ret,mimi(pre-i,pre)+1);
	ret=min(ret,mimi2(max(0,pre-i+1),pre)+1);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	L=S.size();
	strncpy(C,S.c_str(),L);
	C[L]=0;
	MINUS(pat);
	MINUS(pats);
	MINUS(mi);
	MINUS(mis);
	
	lcs(S,S);
	dpdp(0,0);
	
	ll ret=1LL<<50;
	for(i=1;i<=L;i++) if(S[L-i]=='1' && mimi(L-i,L)<6000 && i<=20) ret=min(ret,mimi(L-i,L)+val(L-i));
	for(i=21;i<=L;i++) if(S[L-i]=='1' && mimi(L-i,L)<6000 && ret==1LL<<50) ret=mimi(L-i,L)+val(L-i);
	
	_P("%d\n%lld\n",pat[0][0],ret);
}

まとめ

LCSを用いた前処理による部分文字列の大小判定高速化は、今後も使えそうだな。