AtCoder Beginner Contest 388

## [A - ?UPC](https://atcoder.jp/contests/abc388/tasks/abc388_a)

O(1)

```C++:C++
s.substr(0, 1) + "UPT"
```

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

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    cout << s.substr(0, 1) + "UPC" << endl;
    return 0;
} 
```

## [B - Heavy Snake](https://atcoder.jp/contests/abc388/tasks/abc388_b)

O(K*N)
2重ループです。
シミュレートしましょう。
kを1ずつループで増やして、`T_i * (L_i + k)`を計算し、最も大きな数を求めましょう。

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

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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, D;
    cin >> N >> D;
    vector<int> T(N), L(N);
    rep(i, N) cin >> T[i] >> L[i];
    
    for(int k=1; k<=D; k++){
        int ans = 0;
        for(int i=0; i<N; i++){
            ans = max(T[i] * (L[i] + k), ans);
        }
        cout << ans << endl;
    }
    
    return 0;
} 
```

## [C - Various Kagamimochi](https://atcoder.jp/contests/abc388/tasks/abc388_c)

O(NlogN)
二分探索です。
`b / 2`以下の餅の数を探索します。
upper_boundで`b / 2`以下より一つ大きい要素のイテレータを取得できます。

```C++:C++
ll a = upper_bound(A.begin(), A.end(), b/2) - A.begin();
```

`b / 2`以下の餅の数aを探索できるので、ansでaの合計を求めましょう。

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

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    ll ans = 0;
    for(auto b:A){
        auto a = upper_bound(A.begin(), A.end(), b/2);
        ans += a - A.begin();
    }
    cout << ans << endl;

    return 0;
} 
```

## [D - Coming of Age Celebration](https://atcoder.jp/contests/abc388/tasks/abc388_d)

O(N)
imos法です。

成人した人が何人まで石を渡せるのかを配列Bで管理します。
成人した人が石を渡せる最初の人の要素B[i]に`B[i]++`を行います。
成人した人が石を渡せなくなる人の要素B[i]に`B[i]--`を行います。
ここまで考察すると、imos法だとわかります。

B[i]のiがsizeを超えないように、

```C++:C++
min(i + A[i] + 1, N)
```

A[i]は0未満にならないので、

```C++:C++
A[i] = max(0, A[i] - (N - 1 - i));
```

を行いましょう。

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

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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, 0), B(N+1, 0);

    rep(i, N) cin >> A[i];
    rep(i, N){
        A[i] += B[i];
        B[i+1] += B[i] + 1;
        B[min(i + A[i] + 1, N)]--;
        A[i] = max(0, A[i] - (N - 1 - i));
    }

    rep(i, N){
        cout << A[i];
        if(i<N-1) cout << ' ';
        else cout << endl;
    }
    
    return 0;
} 
```

## [E - Simultaneous Kagamimochi](https://atcoder.jp/contests/abc388/tasks/abc388_e)

O(N)
貪欲法、尺取法です。
N個の餅をN/2に分けます。

```C++:C++
while(b < N && A[i] * 2 > A[b]) b++;
```

A[i] * 2未満の時は、`b`のカウントを進めます。
A[i] * 2以上の時は、`b`、`ans`のカウントを進めます。

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

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    ll ans = 0;
    ll m = N / 2;
    ll b = m;
    for(int i=0; i<m; i++){
        while(b < N && A[i] * 2 > A[b]) b++;
        if(b==N) continue;
        ans++;
        b++;
    }
    cout << ans << endl;

    return 0;
} 
```