AtCoder Beginner Contest c問題, 灰diff埋め

abcが6問題制になってからのc問題, 灰diff埋め。
解説を見ることがなくなりました。

##[C - Prison](https://atcoder.jp/contests/abc127/tasks/abc127_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main() {
    int n, m;
    cin >> n >> m;
    int N[100001]={0};
    
    rep(i, m){
        int l, r;
        cin >> l >> r;
        N[l]++;
        N[r+1]--;
    }
    
    int res=0;
    for(int i=1; i<=n; i++){
        N[i] += N[i-1];
        if(N[i]==m) res++;
    }
    cout << res << endl;
    
    return 0;
}
```

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main() {
    int n, m;
    cin >> n >> m;
    
    int max_l=0;
    int max_r=n;
    rep(i, m){
        int l, r;
        cin >> l >> r;
        max_l = max(max_l, l);
        max_r = min(max_r, r);
    }
    int res = max_r - max_l + 1;
    res = max(res, 0);
    cout << res << endl;
    
    return 0;
}
```

##[C - Divide the Problems](https://atcoder.jp/contests/abc132/tasks/abc132_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main() {
    int n;
    cin >> n;
    
    vector<int> A(n);
    rep(i, n) cin >> A[i];
    sort(A.begin(), A.end());
    ll cnt = A[A.size()/2] - A[A.size()/2-1];
    cout << cnt << endl;
    
    return 0;
}
```

##[C - Exception Handling](https://atcoder.jp/contests/abc134/tasks/abc134_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;


int main() {
    int n;
    cin >> n;
    
    vector<int> A(n);
    vector<int> AA(n);
    rep(i, n) cin >> A[i];
    AA = A;
    sort(AA.begin(), AA.end());
    reverse(AA.begin(), AA.end());
    
    rep(i, n){
        if(A[i] == AA[0]){
            cout << AA[1] << endl;
        }else{
            cout << AA[0] << endl;
        }
    }
    return 0;
}
```

##[C - City Savers](https://atcoder.jp/contests/abc135/tasks/abc135_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;


int main() {
    int n;
    cin >> n;
    
    vector<int> A(n+1);
    vector<int> B(n);
    rep(i, n+1) cin >> A[i];
    rep(i, n) cin >> B[i];
    
    ll res=0;
    rep(i, n){
        if(A[i] - B[i] >= 0){
            res += B[i];
            A[i] -= B[i];
        }else{
            res += A[i];
            B[i] -= A[i];
            if(A[i+1] - B[i] >= 0){
                res += B[i];
                A[i+1] -= B[i];
            }else{
                res += A[i+1];
                A[i+1] = 0;
            }
        }
    }
    cout << res << endl;

    return 0;
}
```

##[C - Build Stairs](hhttps://atcoder.jp/contests/abc136/tasks/abc136_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;


int main() {
    int n;
    cin >> n;
    
    vector<int> H(n);
    rep(i, n) cin >> H[i];
    
    bool res=true;
    int max_h=0;
    for(int i=0; i<n-1; i++){
        if(H[i] > H[i+1]){
            if(H[i]-1 > H[i+1]) res=false;
            if(H[i]-1 < max_h) res=false;
        }
        max_h = max(max_h, H[i]-1);
    }
    if(res) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}
```

##[C - Alchemist](https://atcoder.jp/contests/abc138/tasks/abc138_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;


int main() {
    int n;
    cin >> n;
    
    vector<double> V(n);
    rep(i, n) cin >> V[i];
    sort(V.begin(), V.end());
    
    for(int i=1; i<n; i++){
        V[i] = (V[i]+V[i-1])/2.0;
    }
    cout << fixed_setprecision(10) << V[n-1] << endl;

    return 0;
}
```

##[C - Lower](https://atcoder.jp/contests/abc139/tasks/abc139_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;


int main() {
    int n;
    cin >> n;
    
    vector<int> H(n);
    rep(i, n) cin >> H[i];
    
    int max_left_count=0;
    int left_count=0;
    for(int i=1; i<n; i++){
        if(H[i]<=H[i-1]) left_count++;
        else left_count=0;
        max_left_count = max(max_left_count, left_count);
    }
    cout << max_left_count << endl;
    return 0;
}
```

##[C - Maximal Value](https://atcoder.jp/contests/abc140/tasks/abc140_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;


int main() {
    int n;
    cin >> n;
    
    vector<int> A(n);
    vector<int> B(n-1);
    rep(i, n-1) cin >> B[i];
    
    for(int i=0; i<n; i++){
        if(i==0) A[i] = B[i];
        else if(i==n-1) A[i] = B[i-1];
        else if(i>0) A[i] = min(B[i], B[i-1]);
    }
    
    int res=0;
    rep(i, n) res += A[i];
    cout << res << endl;

    return 0;
}
```

##[C - Attack Survival](https://atcoder.jp/contests/abc141/tasks/abc141_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main() {
    int N, K, Q;
    cin >> N >> K >> Q;
    
    int A[100000]={0};
    rep(i, Q) cin >> A[i];
    
    int P[100001]={0};
    rep(i, N) P[i+1]=K-Q;
    
    for(int i=0; i<Q; i++){
        P[A[i]]++;
    }
    
    for(int i=1; i<=N; i++){
        if(P[i] > 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}
```

##[C - Go to School](https://atcoder.jp/contests/abc142/tasks/abc142_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main() {
    int N;
    cin >> N;
    
    int A[100001]={0};
    rep(i, N){
        int n;
        cin >> n;
        A[n] = i+1;
    }
    rep(i, N) cout << A[i+1] << endl;

    return 0;
}
```

##[C - Slimes](https://atcoder.jp/contests/abc143/tasks/abc143_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main() {
    int N;
    cin >> N;
    
    char S[100000]={' '};
    int cnt=0;
    rep(i, N){
        char s;
        cin >> s;
        if(S[cnt] != s) cnt++;
        S[cnt] = s;
    }
    cout << cnt << endl;

    return 0;
}
```

##[C - Walk on Multiplication Table](https://atcoder.jp/contests/abc144/tasks/abc144_c)

初めは素因数分解かなって考察してたけど、素数の処理で困りました。
灰diffで大変多い（x＾２）を閃くかどうか。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main() {
    ll N;
    cin >> N;
    
    ll max_x=0;
    ll max_y=0;
    for(ll i=2; i*i<=N; i++){
        if(N%i==0){
            max_x = i;
            max_y = N/i;
        }
    }
    
    if(max_x==0 && max_y==0) cout << N-1 << endl;
    else cout << max_x + max_y - 2 << endl;
    
    return 0;
}
```

##[C - Traveling Salesman around Lake](https://atcoder.jp/contests/abc160/tasks/abc160_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main() {
    int K, N;
    cin >> K >> N;
    
    vector<int> A(N);
    vector<int> AA(N);
    rep(i, N){
        cin >> A[i];
        if(i>0 && i < N) AA[i-1] = A[i] - A[i-1];
    }
    AA[N-1] = A[0] + (K - A[N-1]);
    
    sort(AA.begin(), AA.end());
    
    ll res=0;
    rep(i, N-1) res+=AA[i];
    cout << res << endl;

    return 0;
}
```