【ABC358】AtCoder Beginner Contest 358【C++】

コンテスト名

CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358)

コンテストURL

https://atcoder.jp/contests/abc358

開催日

2024/06/15 21:00-22:40

---

A: Welcome to AtCoder Land

解法

• 文字列を比較して判定する

ABC358A.cpp

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

int main(){
    string s, t;
    cin >> s >> t;

    if(s=="AtCoder" && t=="Land"){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    
    return 0;
}

B: Ticket Counter

解法

• $i$ 番目に並んだ人について、 $i-1$ 番目の人がチケットを購入し終わった時間 $F_{i-1}$ で場合分けする
  • $i-1$ 番目の人がチケットを購入し終わった時間 $F_{i-1}$ が $T_i$ より遅ければ、 $F_{i-1}$ から購入手続きを開始する
  • $i-1$ 番目の人がチケットを購入し終わった時間が $T_i$ より早ければ、 $T_i$ から購入手続きを開始する

ABC358B.cpp

#include <iostream>
using namespace std;

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

    int time = 0, t;
    for(int i=0; i<n; i++){
        cin >> t;

        if(time>=t){
            time += a;
        }else{
            time = t + a;
        }

        cout << time << '\n';
    }

    return 0;
}

C: Popcorn

解法

• bit 全探索
  • 順列全探索でも解けるが、 $O(2^N) < O(N!)$ であるため bit 全探索のほうが高速
• どのポップコーン売り場を訪れるかを bit 全探索する
• unordered_set<int> で購入した味を記録する

ABC358C.cpp

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

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

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

    int minv = n;
    for(int i=0; i<(1<<n); i++){
        unordered_set<int> St;
        int cnt = 0;
        for(int j=0; j<n; j++){
            if(i&(1<<j)){
                cnt++;
                for(int l=0; l<m; l++){
                    if(S[j][l]=='o'){
                        St.insert(l);
                    }
                }
            }
        }

        if(St.size()==m){
            minv = min(minv, cnt);
        }
    }

    cout << minv << endl;
    return 0;
}

D: Souvenirs

解法

• ソートしてから二分探索
  • 箱と人の順番は関係ないため、昇順にソートする
• $B_i$ 個以上のお菓子が入った箱のうち、最小個数の箱を二分探索で求める
  • すでにほかの人に渡した箱は選択できないことに注意する

ABC358D.cpp

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

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

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

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    int boxnum = 0, pre = -1;
    long long int sum = 0;
    for(int i=0; i<m; i++){
        boxnum = lower_bound(A.begin(), A.end(), B[i]) - A.begin();
        if(pre>=boxnum){
            boxnum = pre + 1;
        }
        if(boxnum>=n){
            cout << -1 << endl;
            return 0;
        }
        sum += A[boxnum];
        pre = boxnum;
    }

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

E: Alphabet Tiles

解法

• 動的計画法と二項係数
• $\text{dp}[i][j]$ := $i$ 番目までの文字を使って長さ $j$ の文字列を作る組み合わせ数とおく
• $\text{dp}[i][j] \gets \text{dp}[i][j] + \text{dp}[i-1][j-l] \times {}_{j-l+1} \mathrm{H}_l$
  • $i-1$ 番目の文字まで使った長さ $j-l$ の文字列に $i$ 番目の文字を $l$ 個挿入することを考える
  • 挿入場所は重複組み合わせ ${}_{j-l+1} \mathrm{H}_l = \binom{j}{l}$ 通り
• 二項係数の値も $\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}$ より動的計画法で求められる

ABC358E.cpp

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

int main(){
    const int MOD = 998244353;
    int k;
    cin >> k;

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

    vector<vector<long long int>> dp(26+1, vector<long long int>(k+1));
    for(int i=0; i<=26; i++){
        dp[i][0] = 1;
    }

    vector<vector<int>> Com(k+1, vector<int>(k+1));
    Com[0][0] = 1;
    for(int i=1; i<=k; i++){
        Com[i][0] = 1;
        for(int j=1; j<=k; j++){
            Com[i][j] = (Com[i-1][j] + Com[i-1][j-1]) % MOD;
        }
    }

    for(int i=1; i<=26; i++){
        for(int j=1; j<=k; j++){
            for(int l=0; l<=min(j, C[i-1]); l++){
                dp[i][j] += (dp[i-1][j-l]%MOD * Com[j][l]) % MOD;
                dp[i][j] %= MOD;
            }
        }
    }

    long long int sum = 0;
    for(int i=1; i<=k; i++){
        sum += dp[26][i];
        sum %= MOD;
    }

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