【ABC382】AtCoder Beginner Contest 382【C++】

コンテスト名

AtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382）

コンテストURL

開催日

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

---

A: Daily Cookie

解法

• もとから空き箱の個数と $D$ を足す

ABC382A.cpp

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

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

    string s;
    cin >> s;

    int cnt = 0;
    for(int i=0; i<n; i++){
        if(s[i]=='.'){
            cnt++;
        }
    }

    cout << cnt + d << endl;

    return 0;
}

B: Daily Cookie 2

解法

• 問題文通りにシミュレーションする
• 文字列 $S$ を右から順にたどり、 $D$ 個の @ を . に変換する

ABC382B.cpp

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

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

    string s;
    cin >> s;

    int cnt = 0;
    for(int i=n-1; i>=0; i--){
        if(s[i]=='@'){
            cnt++;
            s[i] = '.';
        }
        if(cnt==d){
            break;
        }
    }

    cout << s << endl;

    return 0;
}

C: Kaiten Sushi

解法

• 二分探索

1. 寿司をソートする方法
   • 寿司を美味しさの昇順にソートし、各人が仮に先頭にいた場合に、どの寿司を食べるかを記録する
   • 各人の並び順を考慮し、答えを求める
2. 人をソートする方法
   • 自分より美食度が低い人が前にいる人は、寿司を食べられない
   • 美食度が単調減少になるように、寿司を食べられない人を無視する
   • lower_bound(greater<int>()) で美食度が初めて各寿司の美味しさ $B$ 以下になる人を探索する

ABC382C_1.cpp

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

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

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

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

    vector<int> V(n);
    for(int i=0; i<n; i++){
        int idx = lower_bound(B.begin(), B.end(), make_pair(A[i], 0)) - B.begin();
        V[i] = idx;
    }

    vector<int> ans(m, -1);
    int now = m - 1;
    for(int i=0; i<n; i++){
        if(V[i]>now){
            continue;
        }
        for(int j=V[i]; j<=now; j++){
            auto [bvalue, bidx] = B[j];
            ans[bidx] = i + 1;
        }
        now = V[i] - 1;
    }

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

    return 0;
}

ABC382C_2.cpp

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

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

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

    for(int i=1; i<n; i++){
        A[i] = min(A[i], A[i-1]);
    }

    vector<int> ans(m, -1);
    for(int i=0; i<m; i++){
        int idx = lower_bound(A.begin(), A.end(), B[i], greater<int>()) - A.begin();
        if(idx<n){
            ans[i] = idx + 1;
        }
    }

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

    return 0;
}

D: Keep Distance

解法

• 再帰関数
• $A_N \leqq M$ を満たせないものは枝刈りする

ABC382D.cpp

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

int n, m;
vector<vector<int>> ans;

void f(int cnt, vector<int> &A, int last){
    if(cnt==n){
        ans.push_back(A);
        return;
    }

    for(int i=last+10; i<=m-10*(n-cnt-1); i++){
        A.push_back(i);
        f(cnt+1, A, i);
        A.pop_back();
    }
}

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

    vector<int> first;
    f(0, first, -9);

    cout << ans.size() << endl;
    for(int i=0; i<ans.size(); i++){
        for(int j=0; j<n; j++){
            if(j){
                cout << " ";
            }
            cout << ans[i][j];
        }
        cout << '\n';
    }

    return 0;
}

E: Expansion Packs

解法

• 期待値動的計画法 (DP)
• 1 つのパックに入っているレアカードの枚数の確率分布を求める
  • $\text{dp1}[i][j]$ := $i$ 枚目までで $j$ 枚レアカードが出る確率
  • $\text{dp1}[i+1][j+1]$ += $\text{dp1}[i][j] \times \frac{\text{P}[i]}{100}$
  • $\text{dp1}[i+1][j]$ += $\text{dp1}[i][j] \times (1 - \frac{\text{P}[i]}{100})$
• 開封するパックの個数の期待値を求める
  • $\text{dp2}[i]$ := レアカードが $X$ 枚から残り $i$ 枚の状態で、 $X$ 枚になるまでのパックの個数の期待値
  • $\text{dp2}[i] = 1 + \sum\limits_{j=0}^N \text{dp2}[\max (i-j, 0)] \times \text{dp1}[N][j]$
  • 両辺にある $\text{dp2}[i]$ を移項して、 $\text{dp2}[i] = \frac{1 + \sum\limits_{j=1}^N \text{dp2}[\max (i-j, 0)] \times \text{dp1}[N][j]}{1 - \text{dp1}[N][0]}$

ABC382E.cpp

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

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

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

    vector<vector<double>> dp1(n+1, vector<double>(n+1));
    dp1[0][0] = 1;
    for(int i=0; i<n; i++){
        for(int j=0; j<i+1; j++){
            dp1[i+1][j+1] += dp1[i][j] * P[i]/100.0;
            dp1[i+1][j] += dp1[i][j] * (1 - P[i]/100.0);
        }
    }

    vector<double> dp2(x+1);
    for(int i=1; i<=x; i++){
        dp2[i] += 1;
        for(int j=1; j<=n; j++){
            dp2[i] += dp2[max(i-j, 0)] * dp1[n][j];
        }
        dp2[i] /= 1 - dp1[n][0];
    }

    printf("%.10f\n", dp2[x]);

    return 0;
}