🔵

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

2024/05/12に公開

コンテスト名

AtCoder Beginner Contest 353

コンテストURL

https://atcoder.jp/contests/abc353

開催日

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

Discussion