【ABC405】AtCoder Beginner Contest 405【C++】

コンテスト名

AtCoder Beginner Contest 405（Promotion of AtCoder Career Design DAY）

コンテストURL

開催日

2025/05/10 21:00–22:40

---

A: Is it rated?

解法

• 問題文通りに判定する

ABC405A.cpp

#include <iostream>
using namespace std;

int main(){
    int r, x;
    cin >> r >> x;

    if(x==1){
        if(r>=1600 && r<=2999){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }else if(x==2){
        if(r>=1200 && r<=2399){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }

    return 0;
}

B: Not All

解法

• 問題文通りにシミュレーションする
• vector<int> に各値の要素数を記録する

ABC405B.cpp

#include <iostream>
#include <vector>
using namespace std;

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

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

    bool flag = true;
    for(int i=1; i<=m; i++){
        if(V[i]==0){
            flag = false;
        }
    }

    if(!flag){
        cout << 0 << endl;
        return 0;
    }

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

    return 0;
}

C: Sum of Product

解法

• 計算方法を工夫する
• $\sum\limits_{1 \leqq i \leqq j \leqq N} A_i A_j = \sum\limits_{i=1}^N \left(A_i \times \left( \sum\limits_{j=i+1}^N A_j \right)\right)$
  • $\sum\limits_{j=i+1}^N A_j$ は前の総計 $\sum\limits_{j=i}^N A_j$ から $A_i$ を引くことで $\mathrm{O}(1)$ で求められる

ABC405C.cpp

#include <iostream>
#include <vector>
using namespace std;

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

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

    long long int ans = 0;
    for(int i=0; i<n; i++){
        sum -= A[i];
        ans += A[i] * sum;
    }

    cout << ans << endl;

    return 0;
}

D: Escape Route

解法

• 多始点幅優先探索 (BFS)
  • 最初に、非常口のマスすべてを queue<tuple<char, int, int>> にプッシュしておく
  • 全始点から同時に探索が始まるイメージ
• 非常口から探索しているため、答えの矢印は逆向きになることに注意する

ABC405D.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int main(){
    int h, w;
    cin >> h >> w;

    vector<vector<char>> G(h, vector<char>(w));
    vector<vector<int>> dist(h, vector<int>(w, -1));
    queue<tuple<char, int, int>> Q;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> G[i][j];
            if(G[i][j]=='E'){
                Q.emplace('E', i, j);
                dist[i][j] = 0;
            }
        }
    }

    vector<vector<char>> ans = G;
    vector<char> W = {'v', '<', '^', '>'};
    vector<int> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    while(!Q.empty()){
        auto [c, x, y] = Q.front();
        Q.pop();

        ans[x][y] = c;
        
        for(int j=0; j<4; j++){
            int nx = x + dx[j];
            int ny = y + dy[j];
            if(nx<0 || nx>=h || ny<0 || ny>=w){
                continue;
            }
            if(G[nx][ny]=='#' || G[nx][ny]=='E'){
                continue;
            }

            if(dist[nx][ny]!=-1){
                continue;
            }

            dist[nx][ny] = dist[x][y] + 1;
            Q.emplace(W[j], nx, ny);
        }
    }

    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cout << ans[i][j];
        }
        cout << '\n';
    }

    return 0;
}

E: Fruit Lineup

解法

• 重複組み合わせ ${}_n \mathrm{H}_r = \binom{n+r-1}{r} = \frac{(n+r-1)!}{(n-1)! r!}$
• ブドウより左側にあるバナナの個数を $k$ $(0 \leqq k \leqq C)$ とおくと、答えは $1$ 個のブドウの左右の 2 つの重複組み合わせの積で求められる
  • $A$ 個のリンゴと $k$ 個のバナナが順に並んでおり、その間に $B$ 個のオレンジを挿入する組み合わせ
    • $\binom{(A+k+1)+B-1}{B}$
  • $D$ 個のブドウの間に $C-k$ 個のバナナを挿入する組み合わせ
    • $\binom{D+(C-k)-1}{C-k}$

ABC405E.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long int modinv(long long a, long long m){
	long long int b = m, u = 1, v = 0;

	while(b){
		long long int t = a / b;
		a -= t * b;
        swap(a, b);
		u -= t * v;
        swap(u, v);
	}

	u %= m;

	if(u<0){
        u += m;
    }

	return u;
}

int main(){
    const int MOD = 998244353;
    vector<long long int> V(4000010);

    V[0] = 1;
    for(long long int i=1; i<=4000000; i++){
        V[i] = V[i-1] * i;
        V[i] %= MOD;
    }

    long long int a, b, c, d;
    cin >> a >> b >> c >> d;

    long long int ans = 0;

    for(long long int k=0; k<=c; k++){
        ans += (((V[a+k+1+b-1] * modinv((V[a+k]), MOD) % MOD * modinv((V[b]), MOD))%MOD) * ((V[d+c-k-1] * modinv((V[d-1]), MOD) % MOD * modinv((V[c-k]), MOD))%MOD))%MOD;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}