kmjp's blog

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

Codeforces ECR #169 : G. Substring Compression

問題文はそこまで長くない。
https://codeforces.com/contest/2004/problem/G

問題

1~9で構成される文字列tに対し、f(t)は以下で構築可能な最小の長さの文字列とする。

  • tを2n個の文字列Sに分割する
  • Sから、S[2k+1]をS[2k]回繰り返した文字列を連結した文字列を作る。

ここでN文字の文字列Sと整数Kが与えられる。
SのうちK文字の部分文字列V全通りに対し、それぞれf(V)を求めよ。

解法

分割時の文字列のうち、奇数番目のものは1桁一択である。
また、偶数番目もあまり長く取る必要はない。

1つの文字列に対しこの問題を答える場合、

  • dp(n,d) := n文字のprefixを見たとき、最後の奇数番目の分割した文字がdであるような分割の仕方のうち文字列長の最小値

とするとdは1~9だけ考えればいいことので、O(文字列長)のDPで済む。

ここから、元の問題を考える。
文字列について、以下のテーブルを持つ。

  • その長さと、手前の文字列において、奇数番目の分割した最後の文字がdであり、かつこの文字列を追加したときに奇数番目の分割した最後の文字がeであるような場合の、文字列長の最小値

複数の文字列を連結したとき、両者のテーブルから、連結した文字列に対するテーブルも作成可能である。
こうなるとあとは解答は容易で、元の文字列をK文字ごとに分割し、分割したブロック毎にprefix及びsuffixに対するテーブルを作っておく。

Sのうち各K文字に対する解は、1つのブロックのsuffixと、次のブロックのprefixを連結した文字列に対するテーブルを求めればよい。

struct node {
	int len;
	ll dp[10][10];
};

int N,K;
string S;

node A[404040];
node L[404040];
node R[404040];

node merge(node& L,node& R) {
	if(L.len==0) return R;
	if(R.len==0) return L;
	node M;
	M.len=L.len+R.len;
	int i,j,k;
	FOR(i,10) FOR(j,10) M.dp[i][j]=1LL<<50;
	
	FOR(i,10) FOR(j,10) FOR(k,10) {
		chmin(M.dp[i][k],L.dp[i][j]+R.dp[j][k]);
	}
	return M;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	FOR(i,404040) {
		node& n=A[i];
		if(i<N) {
			n.len=1;
			FOR(j,10) FOR(k,10) n.dp[j][k]=1LL<<50;
			for(j=1;j<10;j++) {
				n.dp[j][j]=j;
				n.dp[j][0]=j;
			}
			n.dp[0][S[i]-'0']=0;
			
		}
		else {
			n.len=0;
		}
	}
	int NB=(N+K-1)/K;
	FOR(i,NB) {
		FOR(j,K) {
			if(j==0) {
				L[i*K+j]=A[i*K];
				R[i*K+j]=A[i*K+K-1];
			}
			else {
				L[i*K+j]=merge(L[i*K+j-1],A[i*K+j]);
				R[i*K+j]=merge(A[i*K+K-1-j],R[i*K+j-1]);
			}
		}
	}
	
	for(i=0;i+K<=N;i++) {
		if(i%K==0) {
			auto v=L[i+(K-1)];
			cout<<v.dp[0][0]<<" ";
		}
		else {
			auto a=R[i/K*K+(K-1-i%K)];
			auto b=L[i/K*K+K+(i%K-1)];
			auto c=merge(a,b);
			cout<<c.dp[0][0]<<" ";
		}
	}
	cout<<endl;
	
	
	
}

まとめ

文字列に対し、スライドしながらK文字に対するなんかしらの値を答える問題で、このブロック分割とprefix/suffixに対するテーブルを持つテクは使えそう。