AtCoder Beginner Contest 376

## [A - Candy Button](https://atcoder.jp/contests/abc376/tasks/abc376_a)

O(N)
シミュレートしましょう。
「前回飴をもらってからの経過時間がC秒未満」とはpreを前回飴をもらった時間として、

```math
pre + C < T_i 
```

で判定できます。

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

    int ans = 1;
    int pre = T[0];
    repx(i, 1, N){
        if(pre + C <= T[i]){
            pre = T[i];
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
} 
```

## [B - Hands on Ring (Easy)](https://atcoder.jp/contests/abc376/tasks/abc376_b)

O(N)
円循環に関する問題です。
L or RをT_iまで移動させる時に２方向ある経路の距離を求めます。
サンプル１を例に考察します。

```
6 3
R 4
L 5
R 6
```

Rから4までの距離を求めましょう。
![B - Hands on Ring (Easy).jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/626801/d44b4140-1e58-ab6f-6e9c-685b3372bc7e.jpeg)

①の経路の距離は、

```
4 - R
```

にて求める事ができます。
②の経路の距離は、円の距離であるNから（4 - R）を減算すると求める事ができます。
式は、

```
N - (4 - R)
```

となります。
この式を展開すると、

```
N - 4 + R
```

となります。
次に２方向ある経路のどちらを使用するか判定する必要があります。
to(T_i)とfrom（L or R）とします。
③の図を見るとLをngとして、

```
from < ng && ng < to
```

の時、「N - 4 + R」の式で距離を計算する事が分かります。
to(T_i)がfrom（L or R）より小さい時は、

```
if(from>to) swap(from, to);
```

と要素を入れ替えて処理をしましょう。
処理を関数化してコーディングしてみましょう。

```C++:C++
auto dist = [&](int from, int to, const int ng){
    if(from > to) swap(from, to);
    if(from < ng && ng < to) return N - to + from;
    return to - from;
};
```

考察ができました。
Qの数だけループをして、dist関数を呼び出すと良さそうです。

```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, Q;
    cin >> N >> Q;
    vector<char> H(Q);
    vector<int> T(Q);
    rep(i, Q) cin >> H[i] >> T[i], T[i]--;

    int ans = 0;
    int L = 0, R = 1;
    rep(i, Q){
        auto dist = [&](int from, int to, const int ng){
            if(from > to) swap(from, to);
            if(from < ng && ng < to) return N - to + from;
            return to - from;
        };

        if(H[i] == 'L'){
            ans += dist(L, T[i], R);
            L = T[i];
        }else{
            ans += dist(R, T[i], L);
            R = T[i];
        }
    }
    cout << ans << endl;

    return 0;
} 
```

## [C - Prepare Another Box](https://atcoder.jp/contests/abc376/tasks/abc376_c)

O(N)
貪欲法の問題です。
購入する箱の最小値を求める問題です。
配列をソートしても答えは変わらないのでソートしましょう。

```
2 3 5 7
2   6 8
```

上記はサンプル１の入力をソートして昇順に並び替えた配列です。
対応するおもちゃと箱を見ます。
購入する箱は3だと分かります。
配列を昇順で判定すると、3のおもちゃを6の箱に入れてしまいます。
購入する箱を3だと判定するためには、昇順で判定するのではなく降順で判定しないといけないです。

```
  2 3 5 7
1   6 8
```

上記はサンプル２の入力をソートして昇順に並び替えた配列です。
1の箱に入るおもちゃがないので、-1が答えになることがわかります。
最も小さいおもちゃから箱に入るか判定していくと答えを求める事ができます。
ここまでの考察で、実装する処理が分かりました。

1. 配列を昇順に並び替える
2. 最も小さいおもちゃから箱に入るか判定する
3. 2の時、箱に入らないおもちゃがあるなら-1を出力
4. 最も大きいおもちゃから箱に入るか判定する
5. 4の時、箱に入らないおもちゃがあるなら、その大きさを出力
6. 1~5までの処理で出力する結果がないなら、最も小さいおもちゃの大きさを出力

```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<int> A(N), B(N-1);
    rep(i, N) cin >> A[i];
    rep(i, N-1) cin >> B[i];

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    for(int i=0; i<N-1; i++){
        if(A[i] > B[i]){
            cout << -1 << endl;
            return 0;
        }
    }

    for(int i=N-1; i>=0; i--){
        if(A[i] > B[i-1]){
            cout << A[i] << endl;
            return 0;
        }
    }
    cout << A[0] << endl;

    return 0;
} 
```

## [D - Cycle](https://atcoder.jp/contests/abc376/tasks/abc376_d)

O(N)
BFSの問題です。
問題文の、
「頂点1を含む閉路が存在するか判定して、存在する場合はそのような閉路のうち辺数が最小の閉路の辺数を求めてください。」
の意味を理解します。
まず閉路とは何か。

```
閉路（circuit, loop, closed path）とは、同じ頂点で始まりかつ終わる、長さ以上の道のことである。
有向閉路，サイクル（cycle）とは、同じ頂点で始まりかつ終わる、長さ以上の有向道のことである。
```

閉路の定義から、
頂点１から各辺をたどり、たどり終わりの点が頂点１の辺が存在するか判定する事と分かります。
また、「辺数が最小の閉路の辺数」とあるので最短経路検索のアルゴリズムだと分かります。
最短経路検索のアルゴリズムは、BFSとダイクストラなどあります。
今回は辺に重みがないのでBFSと判断する事ができます。

```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;
    vector<vector<int>> graph(N, vector<int>());
    rep(i, M){
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
    }

    vector<int> dist(N, 1e9);
    queue<int> que;
    que.push(0);
    dist[0] = 0;

    while(que.size()){
        int p = que.front();
        que.pop();
        for(auto g:graph[p]){
            if(g == 0){
                cout << dist[p] + 1 << endl;
                return 0;
            }else if(dist[g] == 1e9){
                dist[g] = dist[p] + 1;
                que.push(g);
            }
        }
    }
    cout << -1 << endl;

    return 0;
} 
```