🧩 AtCoder Beginner Contest 388

# Info & Summary

• Date: 2025-01-11
• Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ❌ / F ❌ / G ❌
• Problem Type:

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Simulation	Range Update/Prefix Sum	⭐🧠🔥
E	Simulation	Math	🧠
F	Matrix	Matrix	🌀
G	Range Minimum Query (RMQ)	RMQ/Two-pointer/Binary Search	🌀

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 - ?UPC

388A

#include <bits/stdc++.h>

using namespace std;

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

    string s;
    cin >> s;

    cout << s[0] << "UPC" << endl;

    return 0;
}

📌 B - Heavy Snake

388B

#include <bits/stdc++.h>

using namespace std;

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

    int N, D;
    cin >> N >> D;

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

    for (int d = 1; d <= D; d++)
    {
        int ans = 0;
        for (int i = 0; i < N; i++)
        {
            int cur = (L[i] + d) * T[i];
            ans = max(ans, cur);
        }

        cout << ans << endl;
    }

    return 0;
}

📌 C - Various Kagamimochi

388C

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

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

    long long ans = 0;
    for (auto a : A)
    {
        ans += upper_bound(A.begin(), A.end(), a / 2) - A.begin();
    }

    cout << ans << endl;

    return 0;
}

📌 D - Coming of Age Celebration

388D

Tips

By focusing not on receiving but on giving stones, we can find the correct answer by interpreting the problem as follows:

• Alien $i$ has $A_i$ stones and will become an adult $i$ years later
• Alien $i$ gives each of aliens $i + 1, i + 2, ..., N$ a stone(if he has one) in this order when he becomes an adult
• How many stones will they finally have?

Let sequence $C$ of length $N$ be the total number of stones that alien $i$ will recive

Suppose that alien $i$ will give aliens $i + 1, i + 2, ..., R_i$ after becoming an adult. Here, we want to add $1$ to $C_j$ for each $j = i + 1, i + 2, ..., R_i$, but naively doing so costs a total time complexity of $O(N^2)$. Instead we use the cumulative sum trick to optimize it

Let sequence $D$ of length $N + 1$ be the differential sequence of $C$, initially filled with $0$:

• For each $i = 1, 2, ..., N$, do the following:
  • if $i > 1$, let $C_i$ be $C_{i - 1} + D_i$. This determines the number of stones when alien $i$ becomes an adult, yielding $R_i$
  • Add $D_{i + 1}$ to $1$ and $D_{R_i + 1}$ to $-1$

This procedure can be done in a total of $O(N)$ time

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

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

    vector<int> C(N), D(N + 1);

    for (int i = 0; i < N; i++)
    {
        if (i != 0)
        {
            C[i] = C[i - 1] + D[i];
            A[i] += C[i];
        }

        int cnt = min(N - i - 1, A[i]);
        A[i] -= cnt;

        D[i + 1] += 1;
        D[min(N, i + cnt + 1)] -= 1;
    }

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

    return 0;
}

📌 E - Simultaneous Kagamimochi

388E

#include <bits/stdc++.h>

using namespace std;

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

    int N;
    cin >> N;

    deque<int> q;

    for (int i = 0; i < N / 2; i++)
    {
        int a;
        cin >> a;

        q.push_back(a);
    }

    long long ans = 0;
    for (int i = N / 2; i < N; i++)
    {
        int a;
        cin >> a;

        if (q.front() * 2 <= a)
        {
            ans++;
            q.pop_front();
        }
    }

    cout << ans << endl;

    return 0;
}

📌 F - Dangerous Sugoroku

388F

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Simultaneous Kagamimochi 2

388G

Warning

Hard Problems to Tackle Later

// TODO