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

コンテスト名

AtCoder Beginner Contest 353

コンテストURL

開催日

2024/05/11 21:00-22:40

A: Buildings

解法

左から順番に判定して 1 番目のビルより高いビルがあったらプログラム終了

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

解法

問題文通りにシミュレーションする
空席数を記録しておいて先頭グループの人数と比較する
- 空席数が先頭グループの人数より多いなら先頭グループを乗せる
- 空席数が先頭グループの人数より少ないならアトラクションをスタートさせて空席数を $K$ にリセットする

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

解法

二分探索で超過分の組み合わせ数を求める
$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$ となる場合

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

解法

$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() を使用

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;
}