Codeforces #887 : Div1 D. Miriany and Matchstick

これは思いつかないな…。
https://codeforces.com/contest/1852/problem/D

問題

2*Nのグリッドを考える。
1列目にはすでに各セルA,Bのいずれかの文字が埋まっている。
2列目の各セルにA,Bを埋め、隣接セルの文字が異なる数がちょうどKとなるようにできるか。
できるなら一例を示せ。

解法

まず愚直に解くなら、左から順に以下をDPで求めて行き、復元すればよい。
dp(n,l,k) := n列目まで文字を定め、n列に文字lを埋めたとき、隣接セルの文字が異なる数がkとなりうるかどうか

ただしこれだとkをO(N)通り考える必要があり、このDPはO(N^2)かかる。
しかし実際にはdp(n,l,k)がTrueとなるkは区間を成すので、最大値最小値だけ考えるようにすればO(N)で済む。

int T,N,K;
string S;

vector<pair<int,int>> dp[2][202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K>>S;
		
		FOR(i,N-1) if(S[i]!=S[i+1]) K--;
		
		dp[0][0]={{0,0}};
		FOR(i,N) {
			S[i]-='A';
			vector<pair<int,int>> C[2];
			FOR(x,2) {
				FOR(y,2) {
					int sc=(i&&(x!=y))+(S[i]!=y);
					FORR2(a,b,dp[x][i]) {
						C[y].push_back({a+sc,b+sc});
					}
				}
			}
			FOR(x,2) {
				dp[x][i+1].clear();
				sort(ALL(C[x]));
				FORR2(a,b,C[x]) {
					if(dp[x][i+1].empty()||dp[x][i+1].back().second+1<a) {
						dp[x][i+1].push_back({a,b});
					}
					else {
						chmax(dp[x][i+1].back().second,b);
					}
				}
			}
		}
		
		int cx=-1;
		FOR(x,2) {
			FORR2(a,b,dp[x][N]) if(a<=K&&K<=b) cx=x;
		}
		string R;
		if(cx==-1) {
			cout<<"NO"<<endl;
			continue;
		}
		for(i=N-1;i>=0;i--) {
			int ok=0;
			FOR(x,2) if(ok==0) {
				int dif=(i&&(x!=cx))+(cx!=S[i]);
				FORR2(a,b,dp[x][i]) if(a+dif<=K&&K<=b+dif) {
					R+=cx+'A';
					cx=x;
					K-=dif;
					ok=1;
					break;
				}
			}
		}
		reverse(ALL(R));
		cout<<"YES"<<endl;
		cout<<R<<endl;
		
	}
}

まとめ

Trueとなるのが区間となるの、本番中自信をもって通せる気がしないな。