0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@RubyLrving(ruby lrving)

AtCoder Beginner Contest 454

0
Posted at

A - Closed interval

問題文

(r - l + 1)です。
コンテスト中のコードです。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

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

B - Mapping

問題文

全探索。
N人全員が異なる種類の服を着ていますか？
M種類の服全てについて、その服を着ている人が少なくとも1人ずついますか？
を一つずつ判定しましょう。
コンテスト中のコードです。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> f(n);
    rep(i, n) cin >> f[i];

    bool ok = true;
    set<int> st;
    rep(i, n){
        if(st.find(f[i]) != st.end()){
            ok = false;
        }
        st.insert(f[i]);
    }

    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    if(st.size() == m) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

ここでコードを整理しましょう。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> f(n);
    rep(i, n) cin >> f[i];

    set<int> st;
    rep(i, n) st.insert(f[i]);

    if(st.size() == n) cout << "Yes" << endl;
    else cout << "No" << endl;
    if(st.size() == m) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

C - Straw Millionaire

問題文

グラフ問題です。
有向グラフであり、dfs, bfsで解きます。
一度通った辺を管理して通らないようにしましょう。
頂点をsetで管理します。
コンテスト中のコードです。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n, vector<int>());
    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
    }

    vector<bool> used(n, false);
    set<int> st;
    auto dfs = [&](auto dfs, int a)->void{
        if(used[a]) return;
        used[a] = true;
        st.insert(a);
        for(auto b:graph[a]){
            dfs(dfs, b);
        }
    };
    dfs(dfs, 0);
    cout << st.size() << endl;
    return 0;
}

このコードは整理する必要がないでしょう。

D - (xx)

問題文

ポーランド記法、stackに近い問題です。
stackかstringを使用しましょう。
文字が４つ以上ある状態で　(xx)か判定して(と)を取り除くか判定します。
コンテスト中のコードです。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

string cast(string s){
    stack<char> st;
    for(auto c:s){
        if(st.size() > 2 && st.top() == 'x' && c == ')'){
            char t1 = st.top();
            st.pop();
            char t2 = st.top();
            st.pop();
            if(c == ')' && t1 == 'x' && t2 == 'x' && st.top() == '('){
                st.pop();
                st.push(t2);
                st.push(t1);
            }else{
                st.push(t2);
                st.push(t1);
                st.push(c);
            }
        }else{
            st.push(c);
        }
    }
    string t;
    while(st.size()){
        t += st.top();
        st.pop();
    }
    reverse(t.begin(), t.end());
    return t;
}

void solve(){
    string a, b;
    cin >> a >> b;

    string s = cast(a);
    string t = cast(b);

    if(s == t) cout << "Yes" << endl;
    else cout << "No" << endl;
}

int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
    return 0;
}

ここでコードを整理しましょう。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

string cast(string s){
    stack<char> st;
    for(auto c:s){
        st.push(c);

        if(st.size() > 3){
            vector<int> x(4);
            rep(i, 4){
                x[3 - i] = st.top();
                st.pop();
            }

            if(x[0] == '(' && x[1] == 'x' && x[2] == 'x' && x[3] == ')'){
                st.push(x[1]);
                st.push(x[2]);
            }else{
                rep(i, 4) st.push(x[i]);
            }
        }
    }
    string t;
    while(st.size()){
        t += st.top();
        st.pop();
    }
    reverse(t.begin(), t.end());
    return t;
}

void solve(){
    string a, b;
    cin >> a >> b;

    string s = cast(a);
    string t = cast(b);

    if(s == t) cout << "Yes" << endl;
    else cout << "No" << endl;
}

int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
    return 0;
}

stackを使うのやめてみましょう。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

string cast(string s){
    string t;
    for(auto c:s){
        t += c;
        if(t.size() > 3 && t.ends_with("(xx)")){
            t.pop_back();
            t.pop_back();
            t.pop_back();
            t.pop_back();
            t.push_back('x');
            t.push_back('x');
        }
    }
    return t;
}

void solve(){
    string a, b;
    cin >> a >> b;

    string s = cast(a);
    string t = cast(b);

    if(s == t) cout << "Yes" << endl;
    else cout << "No" << endl;
}

int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
    return 0;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?