ABC454の記録

AtCoderBeginnerContest454の感想と自分が解いたところまでの解説を書いていきます
今回はA,B,C,DをC++,をA,B,C,Dをpythonで解きます
AtCoder Beginner Contest 454

1.感想

A問題
簡単
B問題
簡単(1回RE)
C問題
やるだけ
D問題
まあ簡単(時間かけすぎた)
E問題
はい?
yesnoまでならすごい簡単なのに
F問題
知らん
G問題
知らん

2.結果

-1

3.解説

A問題Closed interval

入力してその差+1

pythonでの例

l, r = map(int, input().split())
print(r-l+1)

C++での例

#include <iostream>
using namespace std;

int main(){
    int l, r;
    cin >> l >> r;
    cout << r-l+1 << endl;
}

B問題Mapping

1についてはsetでN種類か
2については配列でMこ全部1以上か
これを出力する

pythonでの例

N, M = map(int, input().split())
A = list(map(int, input().split()))

st = set()
for i in range(N):
    st.add(A[i])
print("Yes" if len(st) == N else "No")

count = [0]*M
for i in range(N):
    count[A[i]-1] += 1
print("Yes" if min(count) > 0 else "No")

C++での例

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for (int& i : A) cin >> i;

    set<int> st;
    for (int i = 0; i < N; i++) st.insert(A[i]);
    cout << (st.size() == N? "Yes": "No") << endl;

    vector<int> count(M, 0);
    for (int i = 0; i < N; i++) count[A[i]-1]++;
    cout << (*min_element(count.begin(), count.end()) > 0? "Yes": "No") << endl;
}

C問題Straw Millionaire

dfsするだけ
stackでやる

pythonでの例

N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(M):
    u, v = map(lambda x: int(x)-1, input().split())
    G[u].append(v)

st = []
visited = [False]*N
st.append(0)
visited[0] = True
while st:
    n = st.pop()
    for i in G[n]:
        if not visited[i]:
            visited[i] = True
            st.append(i)

print(visited.count(True))

C++での例

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; i++){
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
    }

    stack<int> st;
    vector<bool> visited(N, false);
    st.push(0);
    visited[0] = true;
    while (!st.empty()){
        int n = st.top();
        st.pop();
        for (int i : G[n]){
            if (!visited[i]){
                st.push(i);
                visited[i] = true;
            }
        }
    }

    cout << count(visited.begin(), visited.end(), true) << endl;
}

D問題(xx)

stackでやる

pythonでの例

def F(S):
    st = []
    for i in S:
        st.append(i)
        while True:
            n = len(st)
            if n >= 4 and st[-4] == '(' and st[-3] == 'x' and st[-2] == 'x' and st[-1] == ')':
                st.pop()
                st.pop()
                st.pop()
                st.pop()
                st.append('x')
                st.append('x')
            else:
                break
    return st

for _ in range(int(input())):
    A = list(input())
    B = list(input())
    print("Yes" if F(A) == F(B) else "No")

C++での例

#include <iostream>
#include <string>
using namespace std;

string F(string S){
    string st;
    for (char i : S){
        st.push_back(i);
        while (true){
            int n = st.size();
            if (n >= 4 && st.substr(n-4, 4) == "(xx)"){
                st.erase(n-4);
                st += "xx";
            }
            else break;
        }
    }
    return st;
}

int main(){
    int T;
    cin >> T;
    while (T--){
        string a, b;
        cin >> a >> b;
        cout << (F(a) == F(b)? "Yes": "No") << endl;
    }
}