Codeforces ECR #079 : F. New Year and Handle Change

ECRの最終問の割にコードは短い。
https://codeforces.com/contest/1279/problem/F

問題

N文字のアルファベットで書かれた文字列Sと、整数K,Lが与えられる。
文字列中連続するL文字について、全体を大文字か小文字のいずれかにそろえる処理を行うのを、最大K回行える。
min(大文字の数,小文字の数)を求めよ。

解法

入力は具体的なアルファベットは関係なく、大文字か小文字かだけ考えればよい。
K*LがN以上なら全体を大文字か小文字にできるので、その場合は解は自明に0。
それ以外の場合を考える。
小文字を減らすケースと、大文字を減らすケースそれぞれ考えて小さい方を取ろう。

あとは
dp(n,k) := prefix n文字までの間にk回処理を使ったとき、残されたコスト(小文字または大文字の数)
を求めdp(N,K)の最小値を求めればよいが、愚直に行うとO(NK)かかり間に合わない。

ここでAlien DPと呼ぶテクニックを用いる。
ここでは処理を使うコストを二分探索で調整し、使用回数がK回になるようなコストを取る。
そうするとDPの際実行回数を覚えておかなくてよくなり、処理が高速化される。

int N,K,len;
string S;
int A[1010101];
pair<ll,int> D[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>len>>S;
	FOR(i,N) A[i]=(S[i]>='A'&&S[i]<='Z');
	if(1LL*K*len>=N) return _P("0\n");
	
	ll mi=N;
	int loop;
	FOR(loop,2) {
		
		int L=0,R=1<<20;
		ll ret=1LL<<60;
		while(L<R) {
			int M=(R+L)/2;
			FOR(i,N) {
				if(i==0) D[i]={0,0};
				else D[i]=D[i-1];
				D[i].first+=(A[i]^loop);
				
				D[i]=min(D[i], (i>=len) ? make_pair(D[i-len].first+M, D[i-len].second+1) : make_pair((ll)M,1));
			}
			if(D[N-1].second<=K) R=M, ret=max(0LL,D[N-1].first-1LL*K*M);
			else L=M+1;
		}
		mi=min(mi,ret);
		
	}
	cout<<mi<<endl;
}

まとめ

AlienDP、初めて使った。
最大フローの双対系と合わせて、身に着けるのしんどそう。