Codeforces #462 Div2C Div1A A Twisty Movement

問題概要

長さnの数列aが与えられる。
数列aの要素は1,2のどちらか。
区間[l,r](l,rは自由)を1度だけ反転する。
反転した後の数列aにおいて最長の非減少数列の長さを求めよ
(非減少数列は $p_1 < p_2 < ... < p_k$ に対して $a_{p_1} \leq a_{p_2} \leq ... \leq a_{p_k}$ を満たすような数列)

解法

この問題は $O(N) , O(N^2)$ 解法が存在する

$O(N^2)$ 解法

1. Segment Treeで区間に含まれる2(もしくは1)の個数を管理
2. DPで区間[l,r)に含まれる最長の2....21....1(非連続でもよい)を計算する。この2...21...1は[l,r)をひっくり返すと区間[l,r)における最長の非減少数列になる
3. 各l,rに対して[0,l)に含まれる1の数 + [l,r)の最長の2...21...1列 + [r,N)に含まれる2の数を計算する
この計算を行えば3で求めた値の最大値を出力すればよい

これは $O(N^2logN)$ だが、SegmentTreeで管理している部分を累積和とかで管理すれば $O(N^2)$ になる。

struct RSQ{
    public:
        int n;
        vector<int> data;
        RSQ(int n_){
            n = 1;
            while(n<n_) n*=2;
            data.resize(2*n-1);
            for(int i=0;i<2*n-1;i++) data[i]=0;
        }
        void update(int k,int a){
            k+=n-1;
            data[k]=a;
            while(k>0){
                k=(k-1)/2;
                data[k]=data[k*2+1]+data[k*2+2];
            }
        }
        int query(int a,int b,int k,int l,int r){
            if(r<=a or b<=l) return 0;
            if(a<=l and r<=b) return data[k];
            else return query(a,b,k*2+1,l,(l+r)/2)+query(a,b,k*2+2,(l+r)/2,r);
        }
        int query(int a,int b){ return query(a,b,0,0,n); }
};

int main(){
    int N; cin >> N;
    RSQ rsq(N);
    vector<int> a(N);
    rep(i,N){
        cin >> a[i];
        a[i]--;
        rsq.update(i,a[i]);
    }

    vector<vector<int>> dp(N+10,vector<int>(N+10,0));
    rep(i,N+1) dp[i][i+1] = 1;

    for(int len=0;len<=N;len++){
        for(int l=0;l<N;l++){
            int r=l+len;
            if(l+1<N and l<N and l+1<=r and r<=N){
                if(a[l] == 1) chmax(dp[l][r],dp[l+1][r]+1);
                else chmax(dp[l][r],dp[l+1][r]);
            }
            if(r-1>=0 and r-1<N and l<=r-1){
                if(a[r-1] == 0) chmax(dp[l][r],dp[l][r-1]+1);
                else chmax(dp[l][r],dp[l][r-1]);
            }
        }
    }

    ll ans = -1;
    for(int l=0;l<N;l++){
        for(int r=l;r<=N;r++){
            ll tmp = l-rsq.query(0,l)+dp[l][r]+rsq.query(r,N);
            ans = max<ll>(ans,tmp);
        }
    }
    cout<< ans << endl;
}

$O(N)$ 解法

数列aを4つの領域に分割する(領域0,領域1,領域2,領域3とする)。
"領域0に含まれる1の個数 + 領域1に含まれる2の個数 + 領域2に含まれる1の個数 + 領域3に含まれる2の個数"を最大化すればよい。
この領域1と領域2の範囲を反転させることで領域0,領域2の反転,領域1の反転,領域3の順になり、領域0,2から1を、領域1,3から2を選択することで最長の1....12....2を作れる。
具体的な実装は
dp[i][j] := a[i]が領域jに含まれる時、a[i]までで、領域0から領域jまでに最大でいくつ"領域に対応した数字(1,2)"が含まれるか
をもったdpをすれば良い。
更新作業は
dp[i][j]に対して、a[i-1]がどの領域に含まれ、a[i]の数字がなにであるかを考えればよいので、
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + (a[i] == "領域に対応する値")
となる

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i,N) cin >> a[i];

    vector<vector<int>> dp(N+10,vector<int>(4,0));
    if(a[0]==1){
        dp[0][0] = dp[0][2] = 1;
        dp[0][1] = dp[0][3] = 0;
    }else if(a[0]==2){
        dp[0][0] = dp[0][2] = 0;
        dp[0][1] = dp[0][3] = 1;
    }
    for(int i=1;i<N;i++){
        for(int j=0;j<4;j++){
            if(j==0 or j==2){
                if(a[i]==1){
                    chmax(dp[i][j],dp[i-1][j]+1);
                    if(j-1>=0) chmax(dp[i][j],dp[i-1][j-1]+1);
                }else if(a[i]==2){
                    chmax(dp[i][j],dp[i-1][j]);
                    if(j-1>=0) chmax(dp[i][j],dp[i-1][j-1]);
                }
            }else if(j==1 or j==3){
                if(a[i]==1){
                    chmax(dp[i][j],dp[i-1][j]);
                    chmax(dp[i][j],dp[i-1][j-1]);
                }else if(a[i]==2){
                    chmax(dp[i][j],dp[i-1][j]+1);
                    chmax(dp[i][j],dp[i-1][j-1]+1);
                }
            }
        }
    }

    ll ans = -1;
    rep(i,4){
        chmax(ans,dp[N-1][i]);
    }
    cout << ans << endl;
}