AtCoder Beginner Contest 358

A - Welcome to AtCoder Land

O(1)
文字列の比較を行いましょう。

#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() {
    string s, t;
    cin >> s >> t;

    if(s == "AtCoder" && t == "Land") cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
} 

B - Ticket Counter

O(N)
現在の時刻とT[i]を比べて、現在の時刻が過去ならT[i]の時間に更新を行う。
現在の時刻に４を加算します。

#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, A;
    cin >> N >> A;
    vector<int> T(N);
    rep(i, N) cin >> T[i];

    int time = 0;
    rep(i, N){
        if(time <= T[i]){
            time = T[i];
        }
        time += A;
        cout << time << endl;
    }

    return 0;
} 

C - Popcorn

O(2^N)
全探索の問題です。
N個の要素を各個別に使用するか使用しないを決めて、全探索をするのはbit全探索が便利です。

#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<string> S(N);
    rep(i, N) cin >> S[i];

    int ans = N;
    for(int tmp=0; tmp < (1 << N); tmp++){
        bitset<16> bit(tmp);
        int cnt = 0;
        string t;
        rep(i, M) t += 'x';
        rep(i, N){
            if(bit.test(i) == 0){
                continue;
            }
            rep(j, M){
                if(S[i][j] == 'o'){
                    t[j] = 'o';
                }
            }
            cnt++;
        }
        int ok = 1;
        rep(i, M){
            if(t[i] == 'x'){
                ok = 0;
                break;
            }
        }
        if(ok){
            ans = min(ans, cnt);
        }
    }
    cout << ans << endl;

    return 0;
} 

D - Souvenirs

O(NM)
貪欲法です。
AとBをソートしましょう。
その後、最適解の手順を更新処理します。

#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() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N), B(M);
    rep(i, N) cin >> A[i];
    rep(i, M) cin >> B[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    ll cnt = 0;
    ll ans = 0;
    ll j = 0;
    for(int i=0; i<N; i++){
        if(A[i]>=B[j]){
            ans += A[i];
            cnt++;
            j++;
            if(j>=M) break;
        }        
    }

    if(cnt < M) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}