AtCoder Beginner Contest 245

A - Good morning

O(1)
h時間をm分の単位に変換します。
その後、両者の比較を行います。

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 A, B, C, D;
    cin >> A >> B >> C >> D;
 
    if(A * 60 + B < C * 60 + D + 1){
        cout << "Takahashi" << endl;
    }else{
        cout << "Aoki" << endl;
    }
 
    return 0;
}

---

B - Mex

O(N)
setに数列Aを追加。
N＝２０００までの数字をループして、　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;
    cin >> N;
    set<int> st;
    rep(i, N){
        int a;
        cin >> a;
        st.insert(a);
    }
 
    rep(i, 20010){
        if(st.count(i)==0){
            cout << i << endl;
            break;
        }
    }
 
    return 0;
} 

---

C - Choose Elements

O(２N)
N=2*10^5では全探索はできません。
アルゴリズムを使う必要があります。
ぱっと見で動的計画法です。
動的計画法では漸化式を組みましょう！
漸化式は数２Bの数列の単元です。

漸化式

\begin{align*}
& (i==0) A_0 \\
& (i==0) B_0 \\
& (i>0) abs(x_{i-1} - A_i) <= K \\
& (i>0) abs(x_{i-1} - B_i) <= K 
\end{align*}

前の要素を比較して条件を満たしているなら要素を保持します。
重複を避けるためにsetを使用するのが良さそうです。
”vector<set<int>>”のデータ構造を使用しましょう！

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, K;
    cin >> N >> K;

    vector<int> A(N), B(N);
    vector<set<int>> vec(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];
    vec[0].insert(A[0]);
    vec[0].insert(B[0]);

    repx(i, 1, N){
        for(auto v:vec[i-1]){
            if(abs(v - A[i]) <= K){
                vec[i].insert(A[i]);
            }
            if(abs(v - B[i]) <= K){
                vec[i].insert(B[i]);
            }
        }
    }

    if(vec[N-1].size()>0) cout << "Yes" << endl;
    else cout << "No" << endl;
     
    return 0;
} 

---