AtCoder Beginner Contest 043(ABC043) 解説

今日はたくさん更新したいため、やや駆け足の説明で行きます！

A – キャンディーとN人の子供イージー
B – バイナリハックイージー
C – いっしょ
D – アンバランス

A – キャンディーとN人の子供イージー

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

制約が弱いのでforで足してもいいのですが、求めたい和は1+2+3+4+…+Nと、初項1公差1の等差数列の和になります。
和の公式を使えばスラっと書けます。

#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int main(){
    int N;
    cin>>N;
    cout<<N*(N+1)/2<<endl;
}

B – バイナリハックイージー

B - Unhappy Hacking (ABC Edit)

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

説明の通り実装してもよいのですが、’B’の入力で最新の文字を削除することを考えるとstackですんなり書けそうな感じがします。(stackも同様に最新を取り出すため)

#include<bits/stdc++.h>

using namespace std;

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

    stack<char> st;

    for(int i=0;i<s.size();i++){
        if(s[i]=='B'){
            if(!st.empty()) st.pop();
        }
        else st.push(s[i]);
    }

    string ans="";
    while(!st.empty()){
        ans=st.top()+ans;
        st.pop();
    }

    cout<<ans<<endl;
}

C – いっしょ

C - Be Together

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

制約が1<=N<=100,-1<=ai<=100と弱めです。
同じ整数にする値は500とか600にはならず、-100～100の中に納まるはずです。
なので、この問題は愚直に全通り試してminを取ればOKです。

#include<bits/stdc++.h>

using namespace std;

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

    int a[N];

    for(int i=0;i<N;i++){
        cin>>a[i];
    }

    int ans=INT_MAX;
    for(int i=-200;i<=200;i++){
        int c=0;
        for(int j=0;j<N;j++){
            c+=(i-a[j])*(i-a[j]);
        }
        ans=min(ans,c);
    }
    cout<<ans<<endl;
}

-200～200のminを取ってますが、保険で大きくしただけで無駄です…。

D – アンバランス

D - Unbalanced

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

各文字数の時に、過半数が同じ文字になる場合を考えます。

※Xが同じ文字、.が違う文字とする。
2文字　XX
3文字　X.X か XX. か .XX
4文字　.XXX か X.XX か XX.X か XXX.
5文字　..XXX か .X.XX か .XX.X か .XXX. か X..XX か X.X.X か X.XX. か XX..X か XX.X. か XXX..

何となく眺めると、ほとんどの場合で2文字のアンバランス部分文字列の”XX”が含まれていることが分かります。
含まれていないのは、奇数文字で飛ばしで置いたときだけです。(偶数文字では飛ばしで置いても、1文字どこかに置かないといけないので、他のXと隣り合ってしまう。)
よって、アンバランス文字列は文字数に関わらず、

部分文字列にXXかX.Xを含む

と言えます。
よって、上記2つの部分文字列があるかだけを探せばOKです。

#include<bits/stdc++.h>

using namespace std;

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

    for(int i=0;i<s.size()-1;i++){
        if(s[i]==s[i+1]){
            cout<<i+1<<" "<<i+2<<endl;
            return 0;
        }
    }
    for(int i=0;i<s.size()-2;i++){
        if(s[i]==s[i+2]){
            cout<<i+1<<" "<<i+3<<endl;
            return 0;
        }
    }

    cout<<"-1 -1"<<endl;
}

※ちなみに部分点の|S|<=100の場合、愚直解で解けます。
　O(|S|^2)回答です。

#include<bits/stdc++.h>

using namespace std;

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

    for(int i=0;i<s.size();i++){
        for(int k='a';k<='z';k++){
            int c=0;
            for(int j=0;j<s.size();j++){
                if(i+j>=s.size()) break;
                if(k==s[i+j]) c++;
                if(j>=1&&(j+1)/2+1<=c){
                    cout<<i+1<<" "<<i+j+1<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"-1 -1"<<endl;
}