Zenn
🔵

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

2024/12/01に公開
C++
競技プログラミング
AtCoder
アルゴリズム
tech

コンテスト名

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

コンテストURL

https://atcoder.jp/contests/abc382

開催日

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

解法

  • もとから空き箱の個数と 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;
}

解法

  • 問題文通りにシミュレーションする
  • 文字列 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;
}

Discussion