🧩 AtCoder Beginner Contest 372

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Math	Stack	⭐🔥
E	Connected Components	DSU	⚠️🧠🛠️🌀
F	the number of ways	DP	🌀
G	Math	convex hull 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 - delete .

372A

#include <bits/stdc++.h>

using namespace std;

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

    string S;
    cin >> S;

    for (auto c : S)
    {
        if (c != '.')
        {
            cout << c;
        }
    }
    cout << endl;

    return 0;
}

📌 B - 3^A

372B

#include <bits/stdc++.h>

using namespace std;

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

    int M;
    cin >> M;

    vector<int> ans;

    while (M)
    {
        for (int i = 10; i >= 0; i--)
        {
            for (int j = 1; j <= 20; j++)
            {
                int t = pow(3, i);
                if (M >= t)
                {
                    M -= t;
                    ans.push_back(i);
                }
            }
        }

    }

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

    return 0;
}

📌 C - Count ABC Again

372C

#include <bits/stdc++.h>

using namespace std;

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

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

    auto check = [&](int i) -> bool
    {
        return S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C';
    };

    int ans = 0;
    for (int i = 0; i < N - 2; i++)
    {
        ans += check(i);
    }

    for (int i = 0; i < Q; i++)
    {
        int x;
        char c;
        cin >> x >> c;
        x--;

        if (S[x] != c)
        {
            ans -= x < N - 2 && check(x);
            ans -= x < N - 1 && check(x - 1);
            ans -= x >= 2 && check(x - 2);

            S[x] = c;

            ans += x < N - 2 && check(x);
            ans += x < N - 1 && check(x - 1);
            ans += x >= 2 && check(x - 2);
        }

        cout << ans << endl;
    }

    return 0;
}

📌 D - Buildings

372D

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

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

    vector<int> ans(N, 0);

    stack<int> st;
    for (int i = N - 2; i >= 0; i--)
    {
        while (!st.empty() && H[st.top()] < H[i + 1])
        {
            st.pop();
        }
        st.push(i + 1);

        ans[i] = st.size();
    }

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

    return 0;
}

📌 E - K-th Largest Connected Components

372E

#include <bits/stdc++.h>

using namespace std;

struct DSU
{
    vector<int> f, siz;

    DSU() {}
    DSU(int n)
    {
        init(n);
    }

    void init(int n)
    {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x)
    {
        while (x != f[x])
        {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    bool merge(int x, int y)
    {
        x = find(x);
        y = find(y);

        if (x == y)
        {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;

        return true;
    }

    int size(int x)
    {
        return siz[find(x)];
    }
};

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

    int N, Q;
    cin >> N >> Q;

    DSU dsu(N);
    vector<vector<int>> comp(N, vector<int>(10, -1));
    for (int i = 0; i < N; i++)
    {
        comp[i][0] = i + 1;
    }

    for (int i = 0; i < Q; i++)
    {
        int o;
        cin >> o;

        if (o == 1)
        {
            int u, v;
            cin >> u >> v;
            u--;
            v--;

            u = dsu.find(u);
            v = dsu.find(v);

            if (u != v)
            {
                vector<int> x(10, -1);
                int i = 0, j = 0;
                while (i + j < 10)
                {
                    if (comp[u][i] > comp[v][j])
                    {
                        x[i + j] = comp[u][i];
                        i++;
                    } else {
                        x[i + j] = comp[v][j];
                        j++;
                    }
                }

                dsu.merge(u, v);

                comp[u] = x;
            }
        }
        else
        {
            int v, k;
            cin >> v >> k;
            v--;
            k--;

            v = dsu.find(v);

            cout << comp[v][k] << endl;
        }
    }

    return 0;
}

📌 F - Teleporting Takahashi 2

372F

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Ax + By < C

372G

Warning

Hard Problems to Tackle Later

// TODO