自力で解けはしたけど若干苦戦。
http://codeforces.com/contest/477/problem/D
問題
2進数表記の数値xが与えられる。
このxを表記するため、初期値0の整数変数nを用いて以下の処理を繰り返す。
- nの2進数表記を、出力済みの文字列の右に追記する。leading zeroは記載不可。
- 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を用いた前処理による部分文字列の大小判定高速化は、今後も使えそうだな。