🧩 AtCoder Beginner Contest 387

TayLockJanuary 4, 2025About 3 min

🧩 AtCoder Beginner Contest 387

# Info & Summary

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

Problem	Type(s)	Data Structure / Algo	🔥 Key Insight / Mark
D	Shortest Distance	BFS	⭐🔥
E	Constructive	Math	🌀
F	DP	DP	🌀
F	FPS	FPS	🌀

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 - Happy New Year 2025

#include <bits/stdc++.h>

using namespace std;

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

    long long a, b;
    cin >> a >> b;

    cout << a * a + 2 * a * b + b * b << endl;

    return 0;
}

📌 B - 9x9 Sum

#include <bits/stdc++.h>

using namespace std;

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

    int x;
    cin >> x;

    int ans = 0;
    for (int i = 1; i <= 9; i++)
    {
        for (int j = 1; j <= 9; j++)
        {
            ans += (i * j == x ? 0 : i * j);
        }
    }

    cout << ans << endl;

    return 0;
}

In the problem statement, Snake numbers are only defined for integers at least $10$ , but in this editorial, we define that every positive integer less than $10$ is also a Snake number
Define $f(R)$ as the number of integers less than or equal to $R$ , then the sought count can be represented as $f(R) - f(L - 1)$

Suppose that $R$ has $n$ digits in decimal, and its $i$ -th ( $1 \le i \le n$ ) significant digit is $d_i$ . Then, every positive integer $x$ less than or equal to $R$ satisfies exactly one of the following conditions. Conversely, every positive integer $x$ satisfies any of the following is less than or equal to $R$ :

$x = R$ $x = R$
- If $d_1 > d_i$ for all $i$ ( $2 \le i \le n$ ), there is one Snake number
$x$ $x$ has $n$ $n$ digits. Its first $k$ $k$ ( $1 \le k \le n - 1$ $1 \leq k \leq n - 1$ ) digits coincide with those of $R$ $R$ , and the $(k + 1)$ $(k + 1)$ -th one is less than $d_{k + 1}$ $d_{k + 1}$
- If $d_1 \le d_i$ for some $i$ ( $2 \le i \le k$ ), then there are none
- Otherwise, the $(k + 1)$ -th digit should be less than $d_1$ and $d_{k + 1}$ , and the $(k + 2)$ -th and succeeding digits should be less than $d_1$ , so there are $\min(d_1, d_{k + 1}) \times d_1^{n - (k + 1)}$ of them
$x$ $x$ has $n$ $n$ digits. Its first digit is less than $d_1$ $d_{1}$
- The first digit should be between $1$ (inclusive) and $d_1$ (exclusive), and the other digits should be less than it, so there are $\sum_{i = 1}^{d_1 - 1}(i^{n - 1})$ of them
$x$ $x$ has $k$ $k$ digits ( $1 \le k \le n - 1$ $1 \leq k \leq n - 1$ )
- The first digit should be between $1$ and $9$ (inclusive), and the other digits should be less than it, so there are $\sum_{i = 1}^{9}(i^{k - 1})$

// Better version

#include <bits/stdc++.h>

using namespace std;

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

    long long L, R;
    cin >> L >> R;

    auto calc = [&](long long n)
    {
        auto s = to_string(n);
        long long cnt = 0;

        for (int i = 1; i < s.size(); i++)
        {
            for (int x = 1; x <= 9; x++)
            {
                long long res = 1;
                for (int j = 0; j < i - 1; j++)
                {
                    res *= x;
                }

                cnt += res;
            }
        }

        for (int i = 0; i < s.size(); i++)
        {
            for (int x = (i == 0 ? 1 : 0); x < s[i] - '0'; x++)
            {
                if (i == 0 || x < s[0] - '0')
                {
                    int v = i == 0 ? x : s[0] - '0';
                    long long res = 1;
                    for (int j = i + 1; j < s.size(); j++)
                    {
                        res *= v;
                    }

                    cnt += res;
                }
            }

            if (i && s[i] >= s[0])
            {
                break;
            }
        }

        return cnt;
    };

    cout << calc(R + 1) - calc(L) << endl;

    return 0;
}

📌 D - Snaky Walk

#include <bits/stdc++.h>

using namespace std;

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

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

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

    vector<string> grid(H);
    array<int, 2> start;
    for (int i = 0; i < H; i++)
    {
        cin >> grid[i];

        for (int j = 0; j < W; j++)
        {
            if (grid[i][j] == 'S')
            {
                start = {i, j};
            }
        }
    }

    vector<vector<array<int, 4>>> dist(H, vector<array<int, 4>>(W, array<int, 4>{-1, -1, -1, -1}));
    queue<tuple<int, int, int>> q;

    for (int d = 0; d < 4; d++)
    {
        dist[start[0]][start[1]][d] = 0;
        q.push({start[0], start[1], d});
    }

    while (!q.empty())
    {
        auto [x, y, d] = q.front();
        q.pop();

        if (grid[x][y] == 'G')
        {
            cout << dist[x][y][d] << endl;
            return 0;
        }

        for (auto k : {d ^ 1, d ^ 3})
        {
            int nx = x + dx[k];
            int ny = y + dy[k];

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

            if (grid[nx][ny] == '#')
            {
                continue;
            }

            if (dist[nx][ny][k] == -1)
            {
                dist[nx][ny][k] = dist[x][y][d] + 1;
                q.push({nx, ny, k});
            }
        }
    }

    cout << -1 << endl;

    return 0;
}