AtCoder Beginner Contest 402

## [A - CBC](https://atcoder.jp/contests/abc402/tasks/abc402_a)

O(N)
文字列の大文字だけ出力します。
`A=65`、`Z=90`です。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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;
    cin >> S;

    int N = S.size();
    rep(i, N){
        if(65 <= S[i] && S[i] <= 90){
            cout << S[i];
        }
    }
    cout << endl;

    return 0;
} 
```

## [B - Restaurant Queue](https://atcoder.jp/contests/abc402/tasks/abc402_b)

O(N)
データ構造、キューの問題です。
- questが1の時、キューに`x`を追加します
- questが2の時、キューの先頭を表示して、popします

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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;

    queue<int> que;
    rep(i, Q){
        int q;
        cin >> q;

        if(q==1){
            int x;
            cin >> x;
            que.push(x);
        }

        if(q==2){
            int x = que.front();
            que.pop();
            cout << x << endl;
        }
    }

    return 0;
} 
```

## [C - Dislike Foods](https://atcoder.jp/contests/abc402/tasks/abc402_c)

O(N+M+ΣK_i)?
よくわからないです。

自分の解放ではO(NlogN)。
貪欲法？
B_iの値から、M個のsetAを探索してB_iと同じ値の要素を削除するとTLEになります。
B_iの値とM個の配列Aのインデックスを保管するデータ構造を用意しましょう。

１、B_iの値があるM個のsetAのindexを管理するmapを用意します。
２、B_iのループし、mapからindexを管理している配列を取得します。
３、setAからB_iの値を削除します。
４、setのsizeが0ならansにインクリメントします。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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<set<int>> A(M);
    map<int, vector<int>> mp;
    rep(i, M){
        int K;
        cin >> K;
        rep(j, K){
            int a;
            cin >> a;
            A[i].insert(a);
            mp[a].push_back(i);
        }
    }

    vector<int> B(N);
    rep(i, N) cin >> B[i];

    int ans = 0;
    rep(i, N){
        vector<int> num = mp[B[i]];
        for(auto n:num){
            A[n].erase(B[i]);
            if(A[n].size() == 0) ans++;
        }
        cout << ans << endl;
    }

    return 0;
} 
```

すぬけさんの動画にもっと綺麗なコードがあります。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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>> menuList(N);
    vector<int> cnt(M);
    rep(i, M){
        int k;
        cin >> k;
        cnt[i] = k;
        rep(j, k){
            int a;
            cin >> a;
            a--;
            menuList[a].push_back(i);
        }
    }

    int ans = 0;
    rep(i, N){
        int b;
        cin >> b;
        b--;
        for(auto m:menuList[b]){
            cnt[m]--;
            if(cnt[m] == 0) ans++;
        }
        cout << ans << endl;
    }

    return 0;
} 
```

本番中にこのようなコードが書きたいです。

## [D - Line Crossing](https://atcoder.jp/contests/abc402/tasks/abc402_d)

O(N)
数学の問題です。
円周上に等間隔で並ぶ頂点があります。
まず交わる直線の組み合わせを求めるのでなく、全体から平行な直線の組み合わせを引きます。

円周上に等間隔で並ぶ頂点とは？

- 正五角形の頂点ABCDEがあります
    - 直線ADと直線BCは平行ですか
        - いいえ、平行ではありません
- 円周上にある等間隔の頂点ABCDEがあります
    - 直線ADと直線BCは平行ですか
        - はい、平行です

正多角形と円周上にある等間隔の頂点は別物です。
この照明はchat gptに質問する、または数学の参考書を読んでください。
円周上にある等間隔の頂点ABCDEを頂点1, 2, 3, 4, 5とします。
`直線ADと直線BC`は`直線1, 4と直線2, 3`です。

```math
a_1 + b_1 = a_2 + b_2
```

が成り立っています。
`N < a + b`なら`(a + b) % N`を行います。
M個の線分が交わる最大数は、

```math
ans = M * (M - 1) / 2
```

これは漸化式の単元の知識になります。
検索して見て下さい。
`(a+b)%N`の値が同じ線分を探索して、平行な線分の組み合わせをansから引きます。

```C++:C++
    ll ans = M * (M-1) / 2;
    for(auto c:cnt){
        ans -= c * (c-1) / 2;
    }
    cout << ans << endl;
```

考察が終わりました。

```C++:C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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> cnt(N);
    rep(i, M){
        ll a, b;
        cin >> a >> b;
        a--; b--;
        cnt[(a+b)%N]++;
    }

    ll ans = M * (M-1) / 2;
    for(auto c:cnt){
        ans -= c * (c-1) / 2;
    }
    cout << ans << endl;

    return 0;
} 

```