AtCoder Beginner Contest 451

A - illegal

問題文
文字列の長さが5の倍数か判定します。

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 = 5;
    string s;
    cin >> s;

    if(s.size() % n == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
} 

B - Personnel Change

問題文

来季の部門の人数から今季の部門の人数を引きます。

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> a(n), b(n);
    rep(i, n){
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }
    vector<int> ans(m, 0);
    rep(i, n) ans[b[i]]++;
    rep(i, n) ans[a[i]]--;
    rep(i, m) cout << ans[i] << endl;
    return 0;
} 

C - Understory

問題文

データ構造の問題です。
コンテスト中はmultisetで解答しました。

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 q;
    cin >> q;
    multiset<int> mst;
    
    rep(i, q){
        int query, h;
        cin >> query >> h;

        if(query == 1){
            mst.insert(h);
        }

        if(query == 2){
            mst.erase(mst.begin(), mst.upper_bound(h));
        }

        cout << mst.size() << 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 q;
    cin >> q;
    priority_queue<int, vector<int>, greater<int>> pque;
    
    rep(i, q){
        int query, h;
        cin >> query >> h;

        if(query == 1){
            pque.push(h);
        }

        if(query == 2){
            while(pque.size() && pque.top() <= h){
                pque.pop();
            }
        }

        cout << pque.size() << endl;
    }

    return 0;
} 

D - Concat Power of 2

問題文

全列挙の問題です。
10^9以下の2のべき乗は2^29まであります。
29個しかないので全列挙で解答することができると分かります。

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;
    cin >> n;
    vector<int> a;
    ll sum = 1;
    ll INF = 1e9;
    while(sum <= INF){
        a.push_back(sum);
        sum *= 2;
    } 

    set<int> st;
    auto dfs = [&](auto dfs, string s)->void{
        for(auto aa:a){
            string ss = s + to_string(aa);
            ll b = atoll(ss.c_str());
            if(b >= INF) break;
            st.insert(b);
            dfs(dfs, ss);
        }
    };
    dfs(dfs, "");
    auto it = st.begin();
    advance(it, n-1);
    cout << *it << endl;

    return 0;
}