競プロやります。

競プロを頑張るブログです。

トップ > ABC/ARC > AtCoder Beginner Contest 124

AtCoder Beginner Contest 124

ABC/ARC

C - Coloring Colorfully

https://atcoder.jp/contests/abc124/tasks/abc124_c

方針

どの隣り合う 2 枚も異なる色に塗られるため、最終的なタイルの色は

  • 01010101……
  • 10101010……

のどちらかになります。

これらのどちらにするかを両方試して手数を計算し、小さい方を出力します。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    string S; cin >> S;
    int N = S.length();
    // T1 = 01010101……
    // T2 = 10101010…… 
    string T1="", T2="";
    for(int i=0; i<N; i++){
        if(i%2==0){
            T1 += "0";
            T2 += "1";
        }else{
            T1 += "1";
            T2 += "0";
        }
    }

    int cnt1 = 0, cnt2 = 0;
    for(int i=0; i<N; i++){
        if(S[i]!=T1[i]) cnt1++;
        if(S[i]!=T2[i]) cnt2++;
    }
    cout << min(cnt1, cnt2) << endl;
}

D - Handstand

https://atcoder.jp/contests/abc124/tasks/abc124_d
しゃくとり法が割とすぐに浮かびましたが実装で迷走して詰まり、以下の方針に切り替えました。もうちょっと早く解きたかった。

方針

逆立ちした人を直立にする必要はないので、直立→逆立ちの操作のみを行います。

まず、同じ立ち方で連続して並んでいるブロックごとに区切り、各ブロックに何人の人が並んでいるかを数えます。ここで、直立の人は負の数で数え、逆立ちの人は正の数で数えます。このようにしてできた数列を \{a\} とします。 a の長さを n とします。
・入力例 1
S = 00010
a = -3, 1, -1
・入力例 2
S = 11101010110011
a = 3, -1, 1, -1, 1, -1, 2, -2, 2

「負の値を正にする」という操作を最大 K 回繰り返して、正の数の連続した並びを作ります。この問題の目的は、そのような並びに含まれる値の和を最大化することです。
すると、この問題は次のように言い換えられます：「 a の連続した部分列で、中に含まれる負の数が K 個以内のものを全て考える。各部分列の要素の絶対値の総和のうち、最大のものを求めよ」

部分列の区間を [l,r] とします。この中で絶対値の和をとればよいので、区間は出来るだけ広く取るべきです。よって部分列の左端を決めれば、右端も決められそうです。
そこで l = 1,2, \dots n の全通りについて、対応する r と、この区間の a の絶対値の和 T_{l,r} = \sum_{i=l}^{r} |a_i| を求めます。そうして得られた T_{l,r} の中の最大値を出力する方針でいきます。

まずは r を求めます。
a の正負は + - + - + - …… と交互に並んでいることを利用すると、
(1) a_l > 0 のとき
自身は + で、続く - + の並びをK個取ることが出来ます。数列 a の右端よりも右を取ることは出来ないので、 r = \min(n, l + 2K) です。
(2) a_l < 0 のとき
まず - + と並び、続く - + の並びを K-1 個取ることが出来るので、 r = \min(n,l + 1 + 2(K-1)) です。

以上より区間の左端 l を決めたときの右端 r を求めることが出来ました。

次に T_{l,r} を求める必要があります。
区間 [l,r] が定まるごとに |a_l| から |a_r| まで 1 つずつ順番に足し算して和を求めると TLE してしまいます。
そこであらかじめ a の絶対値の累積和 f_i = \sum_{k=1}^{i} |a_k| を計算しておきます。これを用いると T_{l,r} = f_r - f_{l-1} により O(1) で求めることが出来ます。

ソースコード

a の最初に 0 を追加しています。こうすることによって、 l = 1 の場合でも T_{l,r} = f_r - f_{l-1} の式をそのまま使えます。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, K;  cin >> N >> K;
    string S; cin >> S;
    vector<int> a;
    a.push_back(0);
    // a を求める
    for(int i=0; i<N; i++){
        int cnt = 0;
        int j = i;
        while(S[j]==S[i]){
            cnt += (S[i]=='1' ? 1:-1);
            j++;
        }
        a.push_back(cnt);
        i = j-1;
    }
    int n = a.size();

    // a の絶対値の累積和 f を求める
    vector<int> f(n,0); 
    for(int i=0; i<n; i++){
        f[i] = abs(a[i]);
        if(i>0) f[i] += f[i-1];
    }

    int ans = 0;
    for(int l=1; l<n; l++){
        // 区間の右端 r を求める
        int r;
        if(a[l] > 0)
            r = min(n-1, l + 2*K);
        else
            r = min(n-1, l + 1 + 2*(K-1));
        // 区間 [l, r] で a の絶対値の和を求める
        int T_lr = f[r] - f[l-1];
        ans = max(ans, T_lr);
    }
    cout << ans << endl;
}