AtCoder Beginner Contest 茶diff埋め

###[D - Megalomania](https://atcoder.jp/contests/abc131/tasks/abc131_d)

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    vector<P> v(N);

    rep(i,N) cin >> v[i].second >> v[i].first;
    sort(v.begin(), v.end());

    int time=0;
    bool res=true;
    for(int i=0; i<N; i++){
        time+=v[i].second;
        if(time>v[i].first) res = false;
    }
    if(res) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}
```

###[D - Div Game](https://atcoder.jp/contests/abc169/tasks/abc169_d)

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    ll n;
    cin >> n;

    ll value = 2;
    map<int, int> m;
    while(value * value <= n){
        if(n % value == 0){
            n = n / value;
            if(m.find(value) == m.end()) m.insert(make_pair(value, 1));
            else m[value]++;
        }else{
            value++;
        }
    }
    if(n != 1){
        if(m.find(n) == m.end()) m.insert(make_pair(n, 1));
        else m[n]++;
    }

    int res=0;
    for(map<int, int>::iterator itr = m.begin(); itr != m.end(); itr++){
        int cnt=0;
        while(cnt<=itr->second){
            itr->second = itr->second - cnt;
            cnt++;
        }
        res += cnt-1;
    }
    cout << res << endl;

    return 0;
}
```

###[C - Sqrt Inequality](https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_c)

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    long double a, b, c;
    cin >> a >> b >> c;

    long double d = c-a-b;
    if(4*a*b < d*d && d>0) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}
```

###[D - Banned K](https://atcoder.jp/contests/abc159/tasks/abc159_d)

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;

    vector<ll> v(n);
    map<ll, ll> m;
    rep(i, n){
        cin >> v[i];
        m[v[i]]++;
    }

    ll res = 0;
    for(map<ll, ll>::iterator itr = m.begin(); itr != m.end(); itr++){
        res += itr->second * (itr->second - 1) / 2;
    }
    for(int i=0; i<n; i++){
        ll sum = m[v[i]];
        ll v1 = ((sum-1) * (sum-2) / 2);
        ll v2 = (sum * (sum - 1) / 2);
        cout << res + v1 - v2 << endl;
    }

    return 0;
}
```

###[D - Dice in Line](https://atcoder.jp/contests/abc154/tasks/abc154_d)

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int n, k;
    cin >> n >> k;

    vector<long double> v(n+1, 0);
    rep(i, n){
        long double p;
        cin >> p;
        v[i+1] = (p * (p+1) / 2) / p + v[i];
    }

    long double res=0;
    for(int i=k; i<=n; i++){
        res = max(res, v[i] - v[i-k]);
    }
    cout << fixed_setprecision(12) << res << endl;

    return 0;
}
```

###[D - String Formation](https://atcoder.jp/contests/abc158/tasks/abc158_d)

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    string s;
    cin >> s;

    int q;
    cin >> q;

    int cmd, f, is_reverse=0;
    string c;
    rep(i, q){
        cin >> cmd;
        if(cmd==1){
            is_reverse = 1 - is_reverse;
        }else{
            cin >> f >> c;
            if(is_reverse) f = 3 - f;
            if(f==1) s.insert(0, c);
            else s.insert(s.length(), c);            
        }
    }
    if(is_reverse) reverse(s.begin(), s.end());
    cout << s << endl;

    return 0;
}
```

###[D - Prediction and Restriction](https://atcoder.jp/contests/abc149/tasks/abc149_d)

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int n, k;
    cin >> n >> k;
    int r, s, p;
    cin >> r >> s >> p;
    string t;
    cin >> t;

    vector<char> v(n);
    ll res = 0;
    for(int i=0; i<n; i++){
        if((i-k<0 && t[i] == 'r') || (i-k>=0 && t[i] == 'r' && v[i-k] != 'p')){ v[i] = 'p'; res += p; }
        else if((i-k<0 && t[i] == 's') || (i-k>=0 && t[i] == 's' && v[i-k] != 'r')){ v[i] = 'r'; res += r; }
        else if((i-k<0 && t[i] == 'p') || (i-k>=0 && t[i] == 'p' && v[i-k] != 's')){ v[i] = 's'; res += s; }
    }
    cout << res << endl;

    return 0;
}
```

###[D - Triangles](https://atcoder.jp/contests/abc143/tasks/abc143_d)

```C++:C++
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;

    vector<int> v(n, 0);
    rep(i, n) cin >> v[i];

    sort(v.begin(), v.end());

    int res = 0;
    for(int mid=0; mid<n; mid++){
        for(int left=0; left<mid; left++){
            int long_side = v[left] + v[mid];
            int r = lower_bound(v.begin(), v.end(), long_side) - v.begin();
            int l = mid+1;
            res += r - l;
        }
    }
    cout << res << endl;
    return 0;
}
```