🧩 AtCoder Beginner Contest 382

TayLockNovember 30, 2024About 4 min

🧩 AtCoder Beginner Contest 382

# Info & Summary

Date: 2024-12-30
Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ❌ / F ❌ / G ❌
Problem Type:

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Constructive	DFS	⭐🔥
E	DP	Expectation DP	🧠🌀

Details

`Emoji`	`Label`	`Meaning`
⭐	Important	Problem is strategically useful or has reusable patterns
🔥	Must master	Classic problem or technique that appears often and is worth mastering
⚠️	Reattempt	You attempted but failed; worth reviewing and solving again
🧠	New to me	Introduced a new idea, technique, or pattern you hadn’t seen before
🛠️	Template	You built or improved a code template from solving this problem
🌀	Too hard now	Beyond current ability to understand/solve; revisit after more practice

📌 A - Daily Cookie

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, d;
    cin >> n >> d;
    string s;
    cin >> s;

    int num = 0;
    for (auto c : s)
    {
        num += c == '@';
    }

    cout << (n - num) + min(num, d) << endl;

    return 0;
}

📌 B - Daily Cookie 2

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, D;
    string S;
    cin >> N >> D >> S;

    for (int i = N - 1; i >= 0 && D > 0; i--)
    {
        if (S[i] == '@')
        {
            S[i] = '.';
            D--;
        }
    }

    cout << S << endl;

    return 0;
}

📌 C - Kaiten Sushi

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

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

    vector<pair<int, int>> B(M);
    for (int i = 0; i < M; i++)
    {
        int b;
        cin >> b;

        B[i] = {b, i};
    }
    sort(B.rbegin(), B.rend());

    vector<int> ans(M, -1);

    int i = 0, j = 0;
    while (i < N && j < M)
    {
        while (j < M && B[j].first >= A[i])
        {
            ans[B[j].second] = i + 1;
            j++;
        }

        i++;
    }

    for (int i = 0; i < M; i++)
    {
        cout << ans[i] << endl;
    }

    return 0;
}

📌 D - Keep Distance

Tips

A sequence $(A_1)$ of length $1$ is good if and only if $1 \le A_1 \le M - 10(N - 1)$

if $A_1 > M - 10(N - 1)$ , then $A_N$ will exceed $M$ even if it is at its minimum

Tips

Suppose that $2 \le i \le N$ , and that $(A_1, A_2, ..., A_{i - 1})$ is good sequence

Then, the range of $A_i$ such that $(A_1, A_2, ..., A_{i - 1}, A_i)$ is a good sequence if and only if $A_{i - 1} + 10 \le A_i \le M - 10(N - i)$

The problem can be solved by enumerating the good sequence according to this rule

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> ans;

    auto dfs = [&](auto &&self, vector<int> v) -> void {
        int sz = v.size();
        if (sz == N)
        {
            ans.push_back(v);
            return ;
        }

        for (int cur = (sz == 0 ? 1 : v.back() + 10); cur <= M - 10 * (N - sz - 1); cur++)
        {
            vector<int> nxt = v;
            nxt.push_back(cur);
            self(self, nxt);
        }
    };

    dfs(dfs, {});

    int cnt = ans.size();
    cout << cnt << endl;

    for (int i = 0; i < cnt; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << ans[i][j] << " \n"[j == N - 1];
        }
    }

    return 0;
}

📌 E - Expansion Packs

Tips

Let:

$f_i$ : the expected number of packs we need to open to get exactly $i$ more rare cards
$g_j$ : the probability that a pack contains exactly $j$ rare cards

The sought value is $f_X$ , the expected number of packs to collect $X$ rare cards

Tips

We evaluate $f_i$ in the manner of DP:

For $i = 0$ , we have $f_i = 0$
For $i > 0$ , considering the number of rare cards contained in the next pack to open, we can derive $f_i = 1 + \sum_{j = 0}^{N}f_{\max(i - j, 0)} \times g_j$

But, this formula contains $f_i$ on both sides (in $j = 0$ term), so we isolate it:

\begin{align*} f_i &= 1 + f_i \times g_0 + \sum_{j = 1}^{N}f_{\max(i - j, 0)} \times g_j \\ f_i(1 - g_0) &= 1 + \sum_{j = 1}^{N}f_{\max(i - j, 0)} \times g_j \\ f_i &= \frac{1 + \sum_{j = 1}^{N}f_{\max(i - j, 0)} \times g_j}{1 - g_0} \end{align*}

which enables us to find $f_i$ in ascending order of $f_i$ , since all right-hand terms are from earlier states

Therefore, when we know the values $g_j$ , we can compute $f_X$ in a total of $O(NX)$ time

Tips

Let $dp_{i, j}$ : the probability that exactly $j$ rare cards appear in the first $i$ cards in a pack

By summing up the two cases where the $i$ -th card is and is not a rare card, we arrive at:

dp_{i, j} = \frac{P_i}{100} \times dp_{i - 1, j - 1} + (1 - \frac{P_i}{100}) \times dp_{i - 1, j}

We initialize:

$dp_{0, 0} = 1$
$dp_{0, j > 0} = 0$

This DP runs in a total of $O(N^2)$ time, and $g_j = dp_{N, j}$

Note

Time Complexity:

Computing $g_j$ : $O(N^2)$
Computing $f_X$ : $O(NX)$

Total: $O(NX + N^2)$

bottom-up DP

// Step 2: Compute f[i]: expected packs needed to collect i rare cards
vector<double> f(X + 1, 0.0);
for (int i = 1; i <= X; i++)
{
    double sum = 1.0;
    for (int j = 1; j <= N; j++)
    {
        // \sum_{j = 1}^{N}f_{\max(i - j, 0)} \times g_j
        sum += f[max(0, i - j)] * g[j];
    }

    // f_i
    f[i] = sum / (1.0 - g[0]);
}

// DP + memoization

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, X;
    cin >> N >> X;

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

    // Step 1: compute g_j
    vector<double> g(N + 1, 0.0);
    vector<vector<double>> dp(N + 1, vector<double>(N + 1, 0.0));
    dp[0][0] = 1.0;

    for (int i = 1; i <= N; i++)
    {
        double p = P[i - 1] / 100.0;

        for (int j = 0; j <= i; j++)
        {
            // if i-th card is not a rare card
            dp[i][j] += dp[i - 1][j] * (1.0 - p);

            // if i-th card is a rare card
            if (j > 0)
            {
                dp[i][j] += dp[i - 1][j - 1] * p;
            }
        }
    }

    for (int j = 0; j <= N; j++)
    {
        g[j] = dp[N][j];
    }

    // Step 2: compute f_X
    vector<double> memo_f(X + 1, -1.0);
    auto calc_f = [&](auto &&self, int i) -> double
    {
        if (i <= 0)
        {
            return 0.0;
        }
        if (memo_f[i] >= 0.0)
        {
            return memo_f[i];
        }

        // 1 + \sum_{j = 1}^{N}f_{\max(i - j, 0)} \times g_j
        double sum = 0.0;
        sum += 1.0;

        for (int j = 1; j <= N; j++)
        {
            sum += self(self, max(i - j, 0)) * g[j];
        }

        // f_i
        memo_f[i] = sum / (1.0 - g[0]);

        return memo_f[i];
    };

    double ans = calc_f(calc_f, X);

    cout << fixed << setprecision(16) << ans << endl;

    return 0;
}

📌 F - Falling Bars

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Tile Distance 3

Warning

Hard Problems to Tackle Later

// TODO