🧩 AtCoder Beginner Contest 402

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Efficient Counting	Math	⭐
E	Expected Value Optimization	DP/Bottom-Up DP/DFS	🔥🧠
F	Path Enumeration	Meet-in-the-Middle/Bitmask	🔥🛠️

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

402A

#include <bits/stdc++.h>

using namespace std;

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

    string s;
    cin >> s;

    string ans = "";
    for (auto c : s)
    {
        if (isupper(c))
        {
            ans += c;
        }
    }

    cout << ans << endl;

    return 0;
}

📌 B - Restaurant Queue

402B

#include <bits/stdc++.h>

using namespace std;

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

    int Q;
    cin >> Q;

    queue<int> q;

    while (Q--)
    {
        int a;
        cin >> a;

        if (a == 1)
        {
            int x;
            cin >> x;

            q.push(x);
        }
        else
        {
            cout << q.front() << endl;
            q.pop();
        }
    }

    return 0;
}

📌 C - Dislike Foods

402C

#include <bits/stdc++.h>

using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<vector<int>> dish(m, vector<int>());
    vector<vector<int>> has(n, vector<int>());
    vector<int> cnt(m, 0);
    for (int i = 0; i < m; i++)
    {
        int k;
        cin >> k;

        dish[i].resize(k);
        for (int j = 0; j < k; j++)
        {
            cin >> dish[i][j];
            dish[i][j]--;

            has[dish[i][j]].push_back(i);
        }

        cnt[i] = k;
    }


    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int b;
        cin >> b;
        b--;

        for (auto d : has[b])
        {
            cnt[d]--;
            if (cnt[d] == 0)
            {
                ans++;
            }
        }

        cout << ans << endl;
    }

    return 0;
}

📌 D - Line Crossing

402D

Tips

If the direct approach fails, try the opposite: Among the $\frac{M(M - 1)}{2}$ pairs of lines, we will consider the complementary events and count the pairs that do not intersect, the answer can be found as the count subtracted from $\frac{M(M - 1)}{2}$

Tips

Two lines do not intersect if and only if they are parallel

• lines with the same slope are all parallel to each other, if there are $k$ lines with the same slope, then there are $\frac{k(k - 1)}{2}$ pairs of parallel lines
• conversely, any two lines with different slopes always intersect

Therefore, the problem can be solved by classifying the $M$ lines by their slopes

In fact, they can be classified by $(A_i + B_i) \mod N$

Note

This is because, for a line that passes through points $A_i$ and $B_i$, the line passing through the $k$-th point counted clockwise from point $A_i$ and the $k$-th point counted counterclockwise from point $B_i$ is parallel to the line passing through points $A_i$ and $B_i$

#include <bits/stdc++.h>

using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<long long> cnt(n);
    long long ans = 1ll * m * (m - 1) / 2;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;

        ans -= cnt[(a + b) % n];
        cnt[(a + b) % n]++;
    }

    cout << ans << endl;

    return 0;
}

📌 E - Payment Required

402E

💡 Key Observations

• Samll N ($\le 8$): use bitmask DP to represent which problems are already solved
• Large X ($\le 5000$): Add state for remaining money
• State: dp[mask][money] = the maximum expected value when already solved problems in mask and have money left

🧠 State Transition

We try a problem $i$ not yet solved (i.e., $i \notin mask$), if we can afford $C_i$:

• $p = \frac{P_i}{100}$
• if we try it:
  • With prob $p$: we can solve it, get $S_i$ score, and mark it solved
  • With prob $1 - p$: no gain, we can try later if we still have money

#include <bits/stdc++.h>

using namespace std;

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

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

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

    vector<vector<double>> dp(1 << N, vector<double>(X + 1, 0.0));
    vector<vector<bool>> vis(1 << N, vector<bool>(X + 1, false));

    auto dfs = [&](auto &&self, int mask, int left) -> double
    {
        if (vis[mask][left])
        {
            return dp[mask][left];
        }

        vis[mask][left] = true;

        for (int i = 0; i < N; i++)
        {
            if ((mask >> i) & 1)
            {
                // problem i has been solved
                continue;
            }

            if (left >= C[i])
            {
                double p = P[i] / 100.0;

                double expected = p * (self(self, mask | (1 << i), left - C[i]) + S[i]) + (1 - p) * (self(self, mask, left - C[i]));

                dp[mask][left] = max(dp[mask][left], expected);
            }
        }

        return dp[mask][left];
    };

    cout << fixed << setprecision(12) << dfs(dfs, 0, X) << endl;

    return 0;
}

function version

#include <bits/stdc++.h>

using namespace std;

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

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

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

    vector<vector<double>> dp(1 << N, vector<double>(X + 1, 0.0));
    vector<vector<bool>> vis(1 << N, vector<bool>(X + 1, false));

    function<double(int, int)> dfs = [&](int mask, int left) -> double
    {
        if (vis[mask][left])
        {
            return dp[mask][left];
        }

        vis[mask][left] = true;

        for (int i = 0; i < N; i++)
        {
            if ((mask >> i) & 1)
                continue;
            if (left >= C[i])
            {
                double p = P[i] / 100.0;

                double expected = p * (dfs(mask | (1 << i), left - C[i]) + S[i]) + (1 - p) * (dfs(mask, left - C[i]));

                dp[mask][left] = max(dp[mask][left], expected);
            }
        }

        return dp[mask][left];
    };

    cout << fixed << setprecision(12) << dfs(0, X) << endl;

    return 0;
}

Bottom-Up DP version

#include <bits/stdc++.h>

using namespace std;

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

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

    vector<int> S(N), C(N);
    vector<double> P(N);
    for (int i = 0; i < N; i++)
    {
        cin >> S[i] >> C[i] >> P[i];
        P[i] /= 100.0;
    }

    vector<vector<double>> d(1 << N, vector<double>(X + 1, 0.0));

    for (int x = 0; x <= X; x++)
    {
        for (int s = 0; s < (1 << N); s++)
        {
            for (int i = 0; i < N; i++)
            {
                int nx = x - C[i];
                int ns = s | (1 << i);
                if (nx < 0 || s == ns)
                {
                    continue;
                }
                double val = P[i] * (d[ns][nx] + S[i]) + (1 - P[i]) * d[s][nx];
                d[s][x] = max(d[s][x], val);
            }
        }
    }

    cout << fixed << setprecision(12) << d[0][X] << '\n';

    return 0;
}

📌 F - Path to Integer

402F

Tips

If we assume that cell $(i, j)$ has an integer $A_{i, j}10^{2N - i - j}$ written on it instead of a digit $A_{i, j}$, the score becomes the sum of the integers written on each cell modulo $M$

Why?

Because $A_{i, j}$ of cell $(i, j)$ will be at the position of $2 N - i - j$ of the final string

Tips

Notice that when the piece travels from cell $(1, 1,)$ to $(N, N)$, it always visits exactly one of cell $(1, N), (2, N - 1), ..., (N, 1)$

If the piece passes through cell $(k, N + 1 - k)$, then the score is the sum of the following two values, modulo $M$:

• A: The sum of the integers written on the cells visited while traveling from cell $(1, 1)$ to cell $(k, N + 1 - k)$(including)
• B: The sum of the integers written on the cells visited while traveling from cell $(k, N + 1 - k)$(excluding) to cell $(N, N)$

Let:

• $S_1$ be the set of the possible values for A modulo $M$
• $S_2$ be the set of the possible values for B modulo $M$

Then the maximum score is:

$$\max_{x \in S_1, y \in S_2}((x + y) \mod M)$$

Tips

If we fix $x \in S_1$, the value $y \in S_2$ that maximizes $(x + y) \mod M$ is the maximum element among $S_2$ that is strictly less than $M - x$. Such an $y$ can be found fast enough with binary search

By applying this algorithm for all $1 \le k \le N$, the problem can be solved. The time complexity is $O(N2^N)$

#include <bits/stdc++.h>

using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];

            int pow10 = 1;
            int exp = 2 * n - 2 - i - j;
            int base = 10 % m;
            for (int k = 0; k < exp; ++k)
            {
                pow10 = 1LL * pow10 * base % m;
            }

            a[i][j] = 1LL * a[i][j] * pow10 % m;
        }
    }

    int half = n - 1;
    vector<vector<int>> g1(n), g2(n);

    // First half: paths from (0, 0) to row x
    for (int mask = 0; mask < (1 << half); mask++)
    {
        int x = 0, y = 0, sum = 0;
        for (int i = 0; i < half; i++)
        {
            sum = (sum + a[x][y]) % m;
            if (mask >> i & 1)
            {
                x++;
            }
            else
            {
                y++;
            }
        }
        // including cell (k, N + 1 - k)
        sum = (sum + a[x][y]) % m;

        g1[x].push_back(sum);
    }

    // Second half: paths from (n-1, n-1) to row x
    for (int mask = 0; mask < (1 << half); mask++)
    {
        int x = n - 1, y = n - 1, sum = 0;
        for (int i = 0; i < half; i++)
        {
            sum = (sum + a[x][y]) % m;
            if (mask >> i & 1)
            {
                x--;
            }
            else
            {
                y--;
            }
        }

        g2[x].push_back(sum % m);
    }

    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        auto &v1 = g1[i];
        auto &v2 = g2[i];
        sort(v2.begin(), v2.end());

        for (int v : v1)
        {
            int target = m - v;
            auto it = lower_bound(v2.begin(), v2.end(), target);
            if (it != v2.begin())
            {
                --it;
            }

            ans = max(ans, (v + *it) % m);
        }
    }

    cout << ans << endl;

    return 0;
}

📌 G - Sum of Prod of Mod of Linear

402G

Warning

Hard Problems to Tackle Later

// TODO