【ABC353】AtCoder Beginner Contest 353【C++】

### コンテスト名
AtCoder Beginner Contest 353

### コンテストURL
https://atcoder.jp/contests/abc353

### 開催日
2024/05/11 21:00-22:40

---

## [A: Buildings](https://atcoder.jp/contests/abc353/tasks/abc353_a)
**解法**
- 左から順番に判定して 1 番目のビルより高いビルがあったらプログラム終了
```cpp:ABC353A.cpp
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int> H(n);
    for(int i=0; i<n; i++){
        cin >> H[i];
    }

    for(int i=1; i<n; i++){
        if(H[i]>H[0]){
            cout << i+1 << endl;
            return 0;
        }
    }

    cout << -1 << endl;
    return 0;
}
```

## [B: AtCoder Amusement Park](https://atcoder.jp/contests/abc353/tasks/abc353_b)
**解法**
- 問題文通りにシミュレーションする
- 空席数を記録しておいて先頭グループの人数と比較する
    - 空席数が先頭グループの人数より多いなら先頭グループを乗せる
    - 空席数が先頭グループの人数より少ないならアトラクションをスタートさせて空席数を $K$ にリセットする
```cpp:ABC353B.cpp
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;

    vector<int> A(n);
    for(int i=0; i<n; i++){
        cin >> A[i];
    }

    int cnt = 0;
    for(int i=0; i<n; ){
        int vacant = k;
        while(i<n && vacant>=A[i]){
            vacant -= A[i];
            i++;
        }
        cnt++;
    }

    cout << cnt << endl;
    return 0;
}
```

## [C: Sigma Problem](https://atcoder.jp/contests/abc353/tasks/abc353_c)
**解法**
- 二分探索で超過分の組み合わせ数を求める
- $x + y < 10^8$ のとき $f(x, y) = x + y$ 、 $x + y \geqq 10^8$ のとき $f(x, y) = x + y - 10^8$
- $x + y$ の総和を求めて $x + y \geqq 10^8$ となる組み合わせ数分だけ総和から $10^8$ を引く
- 各 $x$ について $x + y \geqq 10^8$ となる $y$ の数をそれぞれ求める
    - 数列 $A$ を昇順にソートして $y \geqq 10^8 - x$ となる $y$ の数を二分探索で求める
    - $x$ 自身が 2 回選ばれる場合を除くことに注意する
        - $x + x \geqq 10^8$ となる場合
```cpp:ABC353C.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;

    const int MOD = 1e8;
    long long int sum = 0;
    vector<int> A(n);
    for(int i=0; i<n; i++){
        cin >> A[i];
        sum += A[i];
    }

    sum *= (n-1);

    sort(A.begin(), A.end());
    long long int cnt = 0;
    for(int i=0; i<n; i++){
        int over = n - (lower_bound(A.begin(), A.end(), MOD-A[i]) - A.begin());
        if(n-over<=i){
            over--;
        }
        cnt += over;
    }

    cnt /= 2;

    cout << sum - MOD * cnt << endl;
    return 0;
}
```

## [D: Another Sigma Problem](https://atcoder.jp/contests/abc353/tasks/abc353_d)
**解法**
- $f(A_i, A_j)$ の各 $A_j$ について考える
    - ある数が連結した値の右側になるときだけを考える
- $A_j$ が連結した値の右側になる回数は $j - 1$ 回
- $A_j$ の桁数を $K_j$ とおく
- $A_j$ が連結した値の右側になるときの総和は $A_j \times (j - 1) + \sum\limits_{i = 1}^{j - 1} A_i \times 10^{K_j}$
    - $A_j \times (j - 1)$ は右側の $A_j$ が何回加算されるか
    - $\sum\limits_{i = 1}^{j - 1} A_i \times 10^{K_j}$ は右側が $A_j$ のときの左側の総和
        - $A_j$ の桁数分だけ左にずれる
        - $\sum\limits_{i = 1}^{j - 1} A_i$ は累積和として先に求めて記録しておく
 - $mod$ の扱いに注意する
     - `modpow()` を使用
```cpp:ABC353D.cpp
#include <iostream>
#include <vector>
using namespace std;

int ketacalc(int x){
    int cnt = 1;
    while(x>=10){
        x /= 10;
        cnt++;
    }
    return cnt;
}

long long int modpow(long long int a, long long int n, long long int m){
	long long int res = 1;
	while(n>0){
		if(n&1){
            res = res * a % m;
        }
		a = a * a % m;
		n >>= 1;
	}
	return res;
}

int main(){
    int n;
    cin >> n;

    const int MOD = 998244353;

    vector<int> A(n);
    for(int i=0; i<n; i++){
        cin >> A[i];
    }

    vector<long long int> S(n+1);
    for(int i=0; i<n; i++){
        S[i+1] += (S[i] + A[i]);
    }

    long long int sum = 0;
    for(int i=1; i<n; i++){
        long long int right = (long long int)A[i] * i;
        long long int left = S[i]%MOD * modpow(10, ketacalc(A[i]), MOD);
        sum += (right + left) % MOD;
        sum %= MOD;
    }

    cout << sum << endl;
    return 0;
}
```