🧩 AtCoder Beginner Contest 407

TayLockMay 24, 2025About 2 min

🧩 AtCoder Beginner Contest 407

# Info & Summary

Date: 2025-05-24
Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ❌ / F ❌ / G ❌
Problem Type:

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
C	Simulation	Math	⭐🧠🔥
D	bitmask, DP	Bitmask DP	⭐🧠🔥
E	Constructive	Constructive	🌀
F	Math		🌀
G	Graph		🌀

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

#include <bits/stdc++.h>

using namespace std;

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

    double A, B;
    cin >> A >> B;

    int ans = (A * 2 + B) / (2 * B);

    cout << ans << endl;

    return 0;
}

📌 B - P(X or Y)

#include <bits/stdc++.h>

using namespace std;

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

    int X, Y;
    cin >> X >> Y;

    double ans = 0.0;

    for (int i = 1; i <= 6; i++)
    {
        for (int j = 1; j <= 6; j++)
        {
            if (i + j >= X || abs(i - j) >= Y)
            {
                ans += (1.0 / 36.0);
            }
        }
    }

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

    return 0;
}

📌 C - Security 2

Tips

For each $1 \le i \le N$ , after pressing button A for the $i$ -th time before pressing it next time, suppose that button B is pressed $b_i$ ( $0 \le b_i \le 9$ ) times

Then, the $j$ -th character of $S_j$ ends up being $S_j$ if and only if $(b_j + ... + b_N) \bmod 10 = S_j$

For $j = N$ , we obviously know $b_N = S_j$ , so we consider $j < N$

By applying the equation $(b_j + ... + b_N) \bmod 10 = S_j$ for the $(j + 1)$ -th character, we obtain:

(b_{j + 1} + ... + b_N) \bmod 10 = S_{j + 1}

Subtracting this from equation above, we obtain:

b_j \equiv S_j - S_{j + 1} (\bmod 10)

Such an integer $b_i$ with $0 \le b_i \le 9$ is uniquely determined as:

(10 + S_j - S_{j + 1}) \bmod 10

Hence, the answer is the sum of $b_j$ over $1 \le j \le N$ , plus $N$

#include <bits/stdc++.h>

using namespace std;

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

    string S;
    cin >> S;

    long long ans = S.size();

    for (int i = S.size() - 1; i >= 0; i--)
    {
        // S_j
        int v = S[i] - '0';
        // S_{j + 1}
        int u = ((i < S.size() - 1) ? S[i + 1] - '0' : 0);

        ans += (10 + v - u) % 10;
    }

    cout << ans << endl;

    return 0;
}

📌 D - Domino Covering XOR

#include <bits/stdc++.h>

using namespace std;

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

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

    // Flatten the H × W grid into a 1D vector grid of size H * W
    vector<long long> grid(H * W);
    for (int i = 0; i < H * W; i++)
    {
        cin >> grid[i];
    }

    long long ans = 0;

    // p: current cell index in 1D (from 0 to H*W-1)
    // mark: a bitmask (integer) that tracks which cells are already covered by a domino
    // cur: current XOR of uncovered cells
    auto dfs = [&](auto &&self, int p, int mask, long long cur) -> void
    {
        // If we have processed all positions, update the global max answer
        if (p == H * W)
        {
            ans = max(ans, cur);
            return;
        }

        // If current cell is already covered, skip it
        if (mask & (1 << p))
        {
            self(self, p + 1, mask, cur);
            return;
        }

        // Option 1: Choose to leave cell p uncovered
        self(self, p + 1, mask, cur ^ grid[p]);
        // Option 2: Try placing a horizontal domino
        if ((p % W) < W - 1 && !(mask & (1 << (p + 1))))
        {
            int temp = (1 << p) | (1 << (p + 1));
            self(self, p + 1, mask | temp, cur);
        }
        // Option 3: Try placing a vertical domino
        if ((p + W) < H * W && !(mask & (1 << (p + W))))
        {
            int temp = (1 << p) | (1 << (p + W));
            self(self, p + 1, mask | temp, cur);
        }
    };

    dfs(dfs, 0, 0, 0);

    cout << ans << endl;

    return 0;
}

📌 E - Most Valuable Parentheses

Warning

Hard Problems to Tackle Later

// TODO

📌 F - Sums of Sliding Window Maximum

Warning

Hard Problems to Tackle Later

// TODO

📌 G - Domino Covering SUM

Warning

Hard Problems to Tackle Later

// TODO