AtCoder Beginner Contest 124(ABC124) 解説

A – Buttons
B – Great Ocean View
C – Coloring Colorfully
D – Handstand

A – Buttons

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

ボタンを押すパターンがA2回、B2回、AB1回ずつの3パターンしかありません。
今回は全パターンの中から最大を求めるようにしました。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int A,B;
    cin>>A>>B;
    cout<<max(max(A+A-1,B+B-1),A+B)<<endl;
}

B – Great Ocean View

B - Great Ocean View

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

Nの最大が20なので、愚直に毎Hiごとに左に高い山がないか調べてもACが取れます。
今回は、左からHiを見ていくついでにHiの最大も保持し、その最大と比較するようにしました。(その最大以上なら、左の山全てより大きいはず)

#include<bits/stdc++.h>

using namespace std;

int main(){
    int N;
    cin>>N;

    int mx;
    cin>>mx;

    int ans=1;
    for(int i=1;i<N;i++){
        int H;
        cin>>H;
        if(H>=mx){
            mx=H;
            ans++;
        }
    }

    cout<<ans<<endl;
}

C – Coloring Colorfully

C - Coloring Colorfully

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

どの隣り合う 2 枚のタイルも異なる色で塗られている
は、言い換えると010101…のように01が交互になるということです。
交互になる場合、始めが0(010101…)か始めが1(101010…)の2パターンしかありません。両方のパターンと比較し、塗り替える数が小さいほうが答えです。

#include<bits/stdc++.h>

using namespace std;

int main(){
    string S;
    cin>>S;

    int ans1=0,ans2=0;
    for(int i=0;i<S.size();i++){
        if(S[i]!=i%2+'0') ans1++;
        if(S[i]!='1'-i%2) ans2++;
    }

    cout<<min(ans1,ans2)<<endl;
}

D – Handstand

D - Handstand

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

“1”を反転させることは悪手です。また、連続している”0″を全て一気に反転しないことも悪手です。
つまり、最善手の反転は連続した”0″を一気に反転させる手です。
なので、この問題は以下のように言い換えられます。

連続した"0"がK個以下であるような、部分列の最大の長さ

今回のように、ある個数をK個以下とする部分列を求めたい場合は尺取り法を使うと上手くいきます。
尺取り法は部分列の右を伸ばしていき、条件の個数に違反した際に、違反しなくなるまで左を伸ばす…を繰り返す方法です。
今回の場合、連続した”0″がK個より大きくなるまで部分列を右に伸ばしていき、K個より大きくなる場合は部分列の左を連続した”0″が1つ消えるまで伸ばしていきます。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int N,K;
    cin>>N>>K;
    string S;
    cin>>S;

    int l=0;
    bool zf=false;
    int c=0;
    if(S[0]=='0'){
        zf=true;
    }

    int ans=0;
    for(int r=0;r<S.size();r++){
        //cout<<l<<","<<r<<","<<c<<endl;
        if(S[r]=='0'){
            if(c==K){
                bool zf2=false;
                if(S[l]==0){
                    zf2=true;
                }
                for(;l<=r;l++){
                    if(S[l]=='0'){
                        zf2=true;
                    }
                    else{
                        if(zf2) break;
                    }
                }
                c--;
            }
            zf=true;
        }
        else{
            if(zf){
                c++;
                zf=false;
            }
        }
        ans=max(ans,r-l+1);
    }

    cout<<ans<<endl;
}

連続した”0″の判定がややこしくて、かなりソースがごちゃっとしちゃいましたね…。