Official

E - Takahashi is Slime 2 Editorial by en_translator

Once a slime is adjacent to Takahashi, the slime remains adjacent unless absorbed. Moreover, his strength never decreases. Thus, he can safely absorb all the slimes that he can.

This leads to the following algorithm:

  • Repeat the following action as many times as possible.
    • Among the adjacent slimes, absorb the one with the smallest strength.

Proof of optimality

Let \(S\) be the slimes absorbed by this algorithm, and assume that absorbing those in a set of slimes \(S ^ {\prime}\) with \(S\neq S ^ {\prime}\) will result in a larger strength.

Here, fix a sequence of moves that absorbs \(S ^ {\prime}\), and consider the slime \(a\) occurring earliest in it such that \(a\in S ^ {\prime}\) and \(a\notin S\). Then, it turns out that when all the elements in \(S\) are absorbed by the algorithm, it is adjacent to \(a\), and Takahashi’s strength at that point is strong enough to absorb \(a\).

This violates \(a\notin S\), so we can conclude that \(S\). \(\square\)

All that left is to implement such a sufficiently fast algorithm.

Whenever a slime is absorbed, there will be at most two more adjacent slimes (it decreases by one, and is newly adjacent to at most three more slimes). Inspecting all the adjacent elements every time you absorb the slime will hardly finish within the execution time limit, but one can manage adjacent slimes in a priority queue or a balanced binary search tree to process a query in \(O(\log HW)\) time.

The number of actions is at most \(HW\), so this is fast enough.

The following is sample code.

#include <iostream>
#include <queue>
#include <ranges>
#include <vector>
#include <limits>

int main() {
    using namespace std;
    unsigned H, W;
    cin >> H >> W;

    unsigned long X;
    unsigned x, y;
    cin >> X >> x >> y;

    // Surround the grid with sentinel slimes whose strengths are too large to absorb
    // 500 × 500 × 10^12 = 2.5 × 10^19 is enough
    vector slime_size(H + 2, vector(W + 2, 250000000000000000UL));
    // Read only the central H x W part
    for (auto &&row : slime_size | views::drop(1) | views::take(H))
        for (auto &&S : row | views::drop(1) | views::take(W))
            cin >> S;

    unsigned long now_size{slime_size[x][y]};

    vector visited(H + 2, vector(W + 2, false));

    priority_queue<tuple<unsigned long, unsigned, unsigned>, vector<tuple<unsigned long, unsigned, unsigned>>, greater<>> pq;
    pq.emplace(0, x, y);
    visited[x][y] = true;

    while (!pq.empty()) {
        const auto [size, x, y] = pq.top();
        pq.pop();

        // If the adjacent slime with the minimum strength is not absorbable, quit
        if (size >= (now_size + X - 1) / X)
            break;

        // Absorb the slime
        now_size += size;

        // Put slimes that are newly adjacent into the priority queue
        for (const auto &[dx, dy] : vector<pair<int, int>>{{1, 0}, {-1, 0}, {0, 1}, {0, -1}})
            if (!visited[x + dx][y + dy]) {
                visited[x + dx][y + dy] = true;
                pq.emplace(slime_size[x + dx][y + dy], x + dx, y + dy);
            }
    }

    cout << now_size << endl;

    return 0;
}

posted:
last update:

OSZAR »