🧩 AtCoder Beginner Contest 384

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Subsequence	Prefix Sum	⭐🔥
E	Grid	BFS	🧠
F	Math	Math	🌀
G	Query square root decomposition	Mo’s Algorithm	🌀

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 - aaaadaa

384A

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    char c1, c2;
    string S;
    cin >> N >> c1 >> c2 >> S;

    for (auto & c : S)
    {
        c = c == c1 ? c1 : c2;
    }

    cout << S << endl;

    return 0;
}

📌 B - ARC Division

384B

#include <bits/stdc++.h>

using namespace std;

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

    int N, R;
    cin >> N >> R;

    for (int i = 0; i < N; i++)
    {
        int d, a;
        cin >> d >> a;

        if (d == 1)
        {
            if (1600 <= R && R <= 2799)
            {
                R += a;
            }
        } else {
            if (1200 <= R && R <= 2399)
            {
                R += a;
            }
        }
    }

    cout << R << endl;

    return 0;
}

📌 C - Perfect Standings

384C

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<pair<int, string>> ans;

    for (int mask = 1; mask < 1 << 5; mask++)
    {
        int score = 0;
        string s = "";

        for (int i = 0; i < 5; i++)
        {
            if (mask >> i & 1)
            {
                score += A[i];
                s += char('A' + i);
            }
        }

        ans.push_back({score, s});
    }

    sort(ans.begin(), ans.end(), [&](auto x, auto y)
         { if (x.first == y.first){
            return x.second < y.second;
         }
        return x.first > y.first; });

    for (auto p : ans)
    {
        cout << p.second << endl;
    }

    return 0;
}

📌 D - Repeated Sequence

384D

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    long long S;
    cin >> N >> S;

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

    vector<long long> pre(2 * N + 1);
    for (int i = 0; i < 2 * N; i++)
    {
        pre[i + 1] = pre[i] + A[i % N];
    }

    S %= pre[N];

    for (int i = 0, j = 0; i <= 2 * N; i++)
    {
        while (pre[i] - pre[j] > S)
        {
            j++;
        }

        if (pre[i] - pre[j] == S)
        {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;

    return 0;
}

📌 E - Takahashi is Slime 2

384E

Tips

Repeat the following action as many times as possible:

• Among the adjacent slimes, absorb the one with the smallest strength

Whenever a slime is absorbed, there will be at most two more adjacent slimes (it decreases by one, and is newly adjacent to at most three more slimes)

Inspecting all the adjacent elements every time you absorb the slime will hardly finish within the execution time limit, but one can manage adjacent slimes in a priority queue or a balanced binary search tree to process a query in $O(\log HW)$ time

The number of actions is at most $HW$, so this is fast enough

#include <bits/stdc++.h>

using namespace std;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

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

    int H, W, X;
    cin >> H >> W >> X;

    int x, y;
    cin >> x >> y;
    x--;
    y--;

    vector<vector<long long>> grid(H, vector<long long>(W));
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> vis(H, vector<bool>(W, false));
    priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<>> pq;

    long long cur = grid[x][y];
    pq.push({0, x, y});
    vis[x][y] = true;

    while (!pq.empty())
    {
        auto [size, x, y] = pq.top();
        pq.pop();

        if (size >= (cur + X - 1) / X)
        {
            break;
        }

        cur += size;

        for (int k = 0; k < 4; k++)
        {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (nx < 0 || ny < 0 || nx >= H || ny >= W)
            {
                continue;
            }
            if (vis[nx][ny])
            {
                continue;
            }

            vis[nx][ny] = true;
            pq.push({grid[nx][ny], nx, ny});
        }
    }

    cout << cur << endl;

    return 0;
}

📌 F - Double Sum 2

384F

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Abs Sum

384G

Warning

Hard Problems to Tackle Later

// TODO