yukicoder : No.1654 Binary Compression

これは自力で解けた。
https://yukicoder.me/problems/no/1654

問題

01で構成される文字列Sが与えられる。
隣接する2文字を選択し、大きくない方を消す、という作業を繰り返し、構築できる文字列は何通りか。

解法

1が1個もない場合は、0を何個残すかなので自明。
以後1が1個以上ある場合を考える。
(いろいろ消した後の)最初の1の前の0と、最後の1の後の0は同様に何個残すかは任意。
あとは最初の1と最後の1に挟まれた部分を考える。

1の後ろにある文字は、0であれ1であれ任意の個数消せる。
そこで、1の後ろに000....000(0がn個)1という文字列をつなげたいと思う場合、S中で0がn個以上初めて連続する箇所の直後の1を貪欲に残すのが良い。

f(n) := Sのprefix n文字までの残し方を決め、かつn文字目が1で残る場合、それ以降の文字の残し方
g(n,k) := Sのn文字目以降で、初めて0がk個以上連続する箇所の食後の1の場所
とおくとf(n)=1+sum(f(g(n,i))となる。
nを大きい順にみて行き、g(n,i)をmapで更新しつつsum(f(g(n,i))を更新していくとよい。

int N;
string S;
const ll mo=924844033;

int len0[3030303];
ll dp[3030303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	
	if(count(ALL(S),'1')==0) {
		cout<<S.size()<<endl;
		return;
	}
	
	int lef=1;
	while(S.back()=='0') {
		S.pop_back();
		lef++;
	}
	
	N=S.size();
	int cur=0;
	FOR(i,N) {
		if(S[i]=='0') {
			cur++;
		}
		else {
			len0[i]=cur+1;
			cur=0;
		}
	}
	map<int,ll> tar;
	ll sum=lef;
	for(i=N-1;i>=0;i--) if(S[i]=='1') {
		dp[i]=sum;
		int pre=0;
		
		while(tar.size()) {
			x=tar.begin()->first;
			y=tar.begin()->second;
			if(x<=len0[i]) {
				(sum-=1LL*(x-pre)*y)%=mo;
				pre=x;
				tar.erase(tar.begin());
			}
			else {
				(sum-=1LL*(len0[i]-pre)*y)%=mo;
				break;
			}
		}
		sum=(sum+mo+len0[i]*dp[i])%mo;
		tar[len0[i]]=dp[i];
	}
	
	cout<<(tar.begin()->first)*(ll)(tar.begin()->second)%mo<<endl;
	
	
}

まとめ

これ系の動き、ライブラリにしようかなぁ。