kmjp's blog

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

Codeforces #893 : Div2 D. Trees and Segments

割と苦戦してるな…。
https://codeforces.com/contest/1858/problem/D

問題

01で構成されるN文字の文字列がある。
整数Aに対し、この文字列のスコアは以下のように計算する。

  • 0が連続する最大数をL0、1が連続する最大数をL1とする。
  • A*L0+L1がスコアとなる。

整数Kが与えられる。
文字列のうちK文字まで0/1反転できるとき、文字列のスコアはどうなるか。
A=1~Nそれぞれについて求めよ。

解法

以下を求めよう。

  • pref0(n,k) := prefix n文字のうちk文字まで01反転したとき、連続する0の最大数
  • suf0(n,k) := suffix n文字のうちk文字まで01反転したとき、連続する0の最大数
  • pref1(n,k) := prefix n文字のうちk文字まで01反転したとき、連続する1の最大数
  • suf1(n,k) := suffix n文字のうちk文字まで01反転したとき、連続する1の最大数

pref0(n,k)とsuf1(N-n,K-k)を突き合せたり、pref1(n,k)とsuf0(N-n,K-k)を突き合わせることで、0の連続数に対し1の連続数の最大値を求めることができる。
あとはそれぞれに対しA=1~Nの時のスコアを計算すればよい。

int T,N,K;
string S;
int L[3030][3030],R[3030][3030];
int LM[3030][3030],RM[3030][3030];
int ret[3030];
int TM[3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K>>S;
		FOR(i,N+1) ret[i]=0;
		
		FOR(x,N+2) FOR(y,N+2) L[x][y]=R[x][y]=0;
		FOR(x,N+2) FOR(y,N+2) LM[x][y]=RM[x][y]=0;
		FOR(i,N+2) TM[i]=-1<<30;
		FOR(i,N) {
			if(S[i]=='0') {
				FOR(j,N+1) {
					L[i+1][j+1]=L[i][j]+1;
				}
			}
			else {
				FOR(j,N+1) L[i+1][j]=L[i][j]+1;
			}
			FOR(j,N+1) {
				LM[i+1][j]=max(LM[i][j],L[i+1][j]);
				if(j) LM[i+1][j]=max(LM[i+1][j],LM[i+1][j-1]);
			}
		}
		for(i=N;i>=1;i--) {
			if(S[i-1]=='0') {
				FOR(j,N+1) {
					R[i][j+1]=R[i+1][j]+1;
				}
			}
			else {
				FOR(j,N+1) {
					R[i][j]=R[i+1][j]+1;
				}
			}
			FOR(j,N+1) {
				RM[i][j]=max(RM[i+1][j],R[i][j]);
				if(j) RM[i][j]=max(RM[i][j],RM[i][j-1]);
			}
		}
		
		TM[0]=LM[N][K];
		FOR(x,N) {
			int fix=0;
			for(y=x;y<N;y++) {
				int len=y-x+1;
				if(S[y]=='1') fix++;
				if(fix<=K) {
					i=max(RM[y+2][K-fix],LM[x][K-fix]);
					TM[len]=max(TM[len],i);
				}
			}
		}
		for(i=0;i<=N;i++) {
			for(x=1;x<=N;x++) ret[x]=max(ret[x],x*i+TM[i]);
		}
		FOR(i,N) cout<<ret[i+1]<<" ";
		cout<<endl;
		
	}
}

解法

わかってしまえばそこまで難しくないのだが。