Atcoder 比赛D题Handstand解析

Atcoder 比赛D题Handstand解析

题目 https://atcoder.jp/contests/abc124/tasks/abc124_d?lang=en

大意:一队人站成一排,所有人不是正立就是倒立,用一个长度等于这队人数的01串表示它们的队。下标为i的字符若为0则表示正立的,为1表示倒立着的人。你可以发K次指令,每次指令是使[l,r]的人状态反过来(正立改倒立,倒立变正立),试求当这样做K次之后,队伍中最多有连续几人处在相同的状态(正立/倒立)

指示を一度行うたびに、人の状態が切り替わる部分を 2 箇所まで潰すことができます。これを踏まえて、連 続して 1 を並ばせる左端を i 番目としたときにいくつ 1 を並べることができるかを考えます。

• Si = 0 のとき: i 番目以降で Sj != Sj+1 となる場所を順に最大 2K − 1 箇所潰すのが最適です。

• Si = 1 のとき: i 番目以降で Sj  != Sj+1 となる場所を順に最大 2K 箇所潰すのが最適です。 1 を並べる左端を i としたときの最大値を Xi とすると、答えは max{X1, X2, …, XN } となります。

しかし、 これをナイーブに実装しても O(N^2 ) となり間に合いません。 そこで、何かしら工夫する必要があります。まず、i (連続して 1 を並ばせる左端) として、元の文字列で 0 または 1 が連続する始点のみを探索すれば十分です。例えば、”11000…” の 4 文字目や 5 文字目の 0 を左端と するよりも 3 文字目の 0 を左端とした方が良いでしょう。このような場所を左から順に 1 = i1 < i2 < … < ir とします。また、便宜上 k > r なる k について、ik = N + 1 とします。このとき、k = 2, 3, …, r について、 Si,k = Si,k−1 です。よって、k = 1, 2, …, r について、Xi,k

• Si,k = 0 のとき: Xi,k = ik+2K − ik

• Si,k = 1 のとき: Xi,k = ik+2K+1 − ik となり、答えは max{Xi,1 , Xi,2 , …, Xi,r } です。これは、O(N) で動作します。 別解として、二分探索を使った O(NlogN) の解法や、しゃくとり法を用いた O(N) の解法もあります。

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int n,k;
    cin >> n >> k;
    string S;
    cin >> S;
    int res = 0;
    int l = 0;
    int cnt = 0;
    for(int r = 0;r < n; r++){
		if(S[r]=='0'){
			if(r==0 || S[r-1]=='1') cnt++;
		}
		if(cnt > k){
			while(l < S.size() && S[l]=='1') l++;
			while(l < S.size() && S[l]=='0') l++;
			cnt--;
		}
		res=max(res,r-l+1);
	}
    
    cout << res << endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注