AtCoder Beginner Contest 362

This article provides solutions and explanations for problems A through E from the ABC 362 contest. Each section includes the problem-solving approach and corrresponding reference implementation.

A - Buy a Pen

Approach

The problem requires determining the minimum cost among two colors based on the selected pen color. Since there are three colors with their respective prices, we simply compute the appropriate minimum value.

Reference Implementation

#include <bits/stdc++.h>

using namespace std;

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

    int red, blue, green;
    cin >> red >> blue >> green;

    string selected;
    cin >> selected;

    if (selected == "Red") {
        cout << min(blue, green) << '\n';
    } else if (selected == "Blue") {
        cout << min(red, green) << '\n';
    } else if (selected == "Green") {
        cout << min(red, blue) << '\n';
    }

    return 0;
}

B - Right Triangle

Approach

We need to verify whether three given points form a right triangle. By the Pythagorean theorem, a triengle is right-angled if the square of the longest side equals the sum of squares of the other two sides. To avoid floating-point precision issues, we work with squared distances directly rather than computing actual distances through square roots.

Reference Implementation

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

struct Point {
    int64 x, y;
};

int64 squaredDistance(const Point& p1, const Point& p2) {
    int64 dx = p1.x - p2.x;
    int64 dy = p1.y - p2.y;
    return dx * dx + dy * dy;
}

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

    Point p1, p2, p3;
    cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y;

    int64 d12 = squaredDistance(p1, p2);
    int64 d13 = squaredDistance(p1, p3);
    int32 = squaredDistance(p2, p3);

    bool isRight = (d12 + d13 == d23) || 
                   (d12 + d23 == d13) || 
                   (d13 + d23 == d12);

    cout << (isRight ? "Yes" : "No") << '\n';

    return 0;
}

C - Sum = 0

Approach

The problem requires constructing a sequence that sums to zero by selecting values within given ranges for each position. We compute the cumulative sums of the left and right boundaries for all positions. If the minimum possible sum (left boundaries) exceeds zero or the maximum possible sum (right boundaries) is below zero, no solution exists.

When a solution is possible, we adjust values to compensate for any deficit. If the left boundary sum is non-positive, we add enough to compensate for the negative offset. Similarly, if the left boundary sum is positive, we reduce values from the right side.

Reference Implementation

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

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

    int n;
    cin >> n;

    int64 leftSum = 0, rightSum = 0;
    vector<pair<int64, int64>> ranges(n);

    for (auto& [left, right] : ranges) {
        cin >> left >> right;
        leftSum += left;
        rightSum += right;
    }

    if (leftSum > 0 || rightSum < 0) {
        cout << "No\n";
        return 0;
    }

    cout << "Yes\n";

    if (leftSum <= 0) {
        int64 deficit = -leftSum;
        for (const auto& [left, right] : ranges) {
            if (deficit > 0) {
                int64 chosen = min(left + deficit, right);
                cout << chosen << ' ';
                deficit -= chosen - left;
            } else {
                cout << left << ' ';
            }
        }
    } else {
        int64 excess = rightSum;
        for (const auto& [left, right] : ranges) {
            if (excess > 0) {
                int64 chosen = max(left, right - excess);
                cout << chosen << ' ';
                excess -= right - chosen;
            } else {
                cout << right << ' ';
            }
        }
    }

    cout << '\n';
    return 0;
}

D - Shortest Path 3

Approach

This is a shortest path problem with an additional node cost. When traversing from node u to node v with edge weight w, the total cost includes the edge weight plus the node weight of the destination node. This varient can be solved using Dijkstra's algorithm with a modified relaxation condition: instead of checking if dis[v] > dis[u] + w, we check if dis[v] > dis[u] + w + a[v], where a[v] represents the node cost.

Reference Implementation

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

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

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

    vector<int64> nodeCost(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> nodeCost[i];
    }

    vector<vector<pair<int, int64>>> graph(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        int64 w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    const int64 INF = LLONG_MAX / 4;
    vector<int64> dist(n + 1, INF);

    using State = pair<int64, int>;
    priority_queue<State, vector<State>, greater<State>> pq;

    dist[1] = nodeCost[1];
    pq.push({dist[1], 1});

    while (!pq.empty()) {
        auto [currentDist, u] = pq.top();
        pq.pop();

        if (currentDist != dist[u]) continue;

        for (const auto& [v, w] : graph[u]) {
            int64 newDist = currentDist + w + nodeCost[v];
            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.push({newDist, v});
            }
        }
    }

    for (int i = 2; i <= n; ++i) {
        cout << dist[i] << (i == n ? '\n' : ' ');
    }

    return 0;
}

E - Count Arithmetic Subsequences

Approach

We need to count the number of arithmetic subsequences of each length. Dynamic programming provides an efficient solution. Let dp[len][j][k] represent the number of arithmetic subsequences of length len ending with elements at positions j and k (where j < k). The common difference is determined by the last two elements.

For transitions, we consider extending a subsequence of length len-1 ending at positions (i, j) by adding element at position k. This is valid only if the common difference remains consistent: a[j] - a[i] == a[k] - a[j].

We accumulate results for each length and apply modular arithmetic with mod = 998244353.

Reference Implementation

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

constexpr int64 MOD = 998244353;
constexpr int MAXN = 305;

int64 dp[MAXN][MAXN][MAXN];

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

    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }

    vector<int64> result(n + 1);
    result[1] = n;
    result[2] = (int64)n * (n - 1) / 2;

    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            dp[2][i][j] = 1;
        }
    }

    for (int len = 3; len <= n; ++len) {
        for (int j = len - 1; j <= n; ++j) {
            for (int k = j + 1; k <= n; ++k) {
                for (int i = len - 2; i < j; ++i) {
                    if (a[j] - a[i] == a[k] - a[j]) {
                        dp[len][j][k] = (dp[len][j][k] + dp[len - 1][i][j]) % MOD;
                    }
                }
                result[len] = (result[len] + dp[len][j][k]) % MOD;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << result[i] << (i == n ? '\n' : ' ');
    }

    return 0;
}