AtCoder Beginner Contest 241

## [A - Digit Machine](https://atcoder.jp/contests/abc241/tasks/abc241_a)

O(1)

```C++: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=10;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
 
    cout << A[A[A[0]]] << endl;
 
    return 0;
}
```

## [B - Pasta](https://atcoder.jp/contests/abc241/tasks/abc241_b)

O(N)
連想配列でパスタの長さを計測。
次に使用するパスワの長さを減算。
０以下ならNo。

```C++: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;
 
    map<int, int> mp;
    rep(i, N){
        int a;
        cin >> a;
        mp[a]++;
    }
 
    int ok=1;
    rep(j, M){
        int b;
        cin >> b;
        mp[b]--;
        if(mp[b]<0){
            ok=0;
            break;
        }
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
 
    return 0;
} 
```

## [C - Connect 6](https://atcoder.jp/contests/abc241/tasks/abc241_c)

O(N)
実装問題です。
ある地点から、横、縦、斜めの＃の数をカウントします。
４以上ならOKです。

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

    int ok=0;
    rep(i, N){
        rep(j, N){
            int cnt_x=0;
            int cnt_y=0;
            int cnt_r=0;
            int cnt_l=0;
            for(int p=0; p<6; p++){
                if(j+5<N && S[i][j+p]=='#') cnt_x++;
                if(i+5<N && S[i+p][j]=='#') cnt_y++;
                if(i+5<N && j+5<N && S[i+p][j+p]=='#') cnt_r++;
                if(i+5<N && j-5>=0 && S[i+p][j-p]=='#') cnt_l++;
            }

            if(cnt_x>=4 || cnt_y>=4 || cnt_r>=4 || cnt_l>=4){
                ok=1;
                break;
            }
        }
        if(ok) break;
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
} 
```

## [D - Sequence Query](https://atcoder.jp/contests/abc241/tasks/abc241_d)

O(NlogN)
二分探索の問題です。
数値を昇順に管理する必要があるのでmultisetを使用します。
その後、二分探索を行います。

```C++: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<ll> st;
    multiset<ll>::iterator it;
    rep(i, Q){
        ll c, x, k;
        cin >> c;
        if(c==1){
            cin >> x;
            st.insert(x);
        }else if(c==2){
            cin >> x >> k;
            it = st.upper_bound(x);
            while(k>0){
                if(st.begin() == it) break;
                it--;
                k--;
            }
            if(k==0 && st.end() != it) cout << *it << endl;
            else cout << -1 << endl;
        }else{
            cin >> x >> k;
            it = st.lower_bound(x);
            k--;
            while(k>0){
                if(st.end() == it) break;
                it++;
                k--;
            }
            if(k==0 && st.end() != it) cout << *it << endl;
            else cout << -1 << endl;
        }
    }

    return 0;
} 
```