AtCoderBeginerContest322 A~C問題まで解いてみた

ABC322

A~Cまで3問解きました。
AtCoderのC++の解説サイト(APG4みたいなやつ)から勉強を始めたので、同じように始めた方は少しだけコードが読みやすいかもしれません(よく他人のc++コードみるけど書き方違いすぎて理解が難しい)。B問題は汚くなりました。
C問題はqueueで実装してみました。

A - FirstABC2

ポイント？：文字列はstring型で受け取るんだけど、その中身は1文字ずつの値が集まった配列とみなすことができる。そのためstring s = "abcde"だったら、a[2]で"c"にアクセスできる。

S[i],S[i+2],S[i+3]の隣り合う3文字がABCになるかどうか判定します。
一番左の文字から、最後から3番目の文字までを確認して、最初にABCを発見したらfor文を終了します
他にもfind("文字列")とすると、該当する文字列の出現位置を返してくれるのでこっちのほうが簡単にかけますね。

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

int main(void){
    int N; cin >> N;
    string S; cin >> S;
    
    int ans = -1;
    
    for(int i = 0; i < N-2; i++){
        if(S[i]=='A' && S[i+1] == 'B' && S[i+2] == 'C'){
            ans = i+1;
            break;
        }
    }
    cout << ans << endl;
    
    return 0;
}

B - Prefix and Suffix

ポイント：文字列操作がある程度わかっていれば解ける。文字列操作についていい感じにまとめてあったもののリンク張っときます。

文字列Sと文字列Tがあり、SとTの先頭が一致するとき、
SとTの語尾が一致するとき、をそれぞれ調べます。

結構強引に書いていて、
先頭の方は、T.substr(0,N)とすることでTの文字列からSと同じ長さを引っ張ってきて同じかどうか判定しています。
語尾の方は、一度reverseして文字列反転させて先頭からSと同じ長さをTから切り取って、それをまたreverseで文字列反転させてからSと同じかどうか判定しています。

コードもみにくいし全然スマートじゃない、、、、、、次回以降改善に期待！

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

int main(void){
    int N,M; cin >> N >> M;
    string S; cin >> S;
    string T; cin >> T;
    
    string S_T = T.substr(0,N);
    string rev_S = S;
    reverse(rev_S.begin(),rev_S.end());
    
    string rev_T = T;
    reverse(rev_T.begin(),rev_T.end());
    string T_S = rev_T.substr(0,N);
    
    if(S == S_T && rev_S == T_S){
        cout << 0 << endl;
    }else if(S == S_T){
        cout << 1 << endl;
    }else if(rev_S == T_S){
        cout << 2 << endl;
    }else{
        cout << 3 << endl;
    }
    
    
    return 0;
}

C - Festival

ポイント？：多分AtCoderのC問題以上は、計算量を意識してかかないと正解できない。この問題は始め愚直に実装したらTLEになって再度考えなおしました。

[1,3,4,7,8]
この例の場合,
1~8日目についてそれぞれ
[1-1,3-1,3-2,3-3,4-4,7-5,7-6,7-7,8-8]
[0,1,0,0,2,1,0,0]

1日目なら、1以上で最小の値1と引き算=0
2日目なら、2以上で最小の値3と引き算
5日目なら、5以上で最小の値7と引き算
6日目なら、6以上で最小の値7と引き算
7日目なら、7以上で最小の値7と引き算=0

このように、n日目の時点でn日目以上のなかで最小の数字とn自身を引き算したら求まります

ちょうど最近勉強したデータ構造のqueueを使って実装しています。
queueにデータを入れると先頭(front)に格納され、データを出すときはpop()を使うと先頭のデータから出ていかせることができます。

これを使って、もし"n日目以降で初めて花火があがる日がnから数えて0日目"なら、先頭にある数は今後一生使わないのでpopして消し去ります。

他の解法としては、後ろから順にみていくことで2重ループが発生せずにACできるやり方が公式で解説されていましたね。

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

int main(void){
    int N,M; cin >> N >> M;
    
    queue<int> A; //queue<データ型> 配列名;で作成
    for(int i = 0; i < M; i++){
        int a;
        cin >> a;
        A.push(a); //queueへのデータ登録は配列名.push(値)
    }
    
    for(int i = 1; i <= N; i++){
        int x = A.front() - i; //配列の先頭の要素を呼び出す 配列名.front()
        cout << x << endl;
        if(x == 0) A.pop();
    }
    
    return 0;
}