実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1004

問題概要

$H \times W$ のマス目があり、上から $i$ 行目、左から $j$ 列目のマスをマス $(i, j)$ と呼ぶ。

はじめ、マス $(i, j)$ には強さ $S_{i,j}$ のスライムがおり、マス $(P,Q)$ にいるスライムが高橋くんである。高橋君が以下の行動を0回以上行ったあとの、高橋君の強さとしてありえる最大値を求めよ。なお、この行動の際、スライムが吸収され消滅したことで生じた隙間は直ちに高橋君によって埋められ、消滅したスライムに隣接していたスライム (それらが存在すれば) は新たに高橋君と隣接する。

高橋くんに隣接するスライムのうち、強さが高橋くんの強さの $\frac{1}{X}$ 倍未満のものを選んで吸収する。その結果、吸収されたスライムは消滅し、高橋君の強さは吸収したスライムの強さだけ増加する。

制約

入力はすべて整数。
$1\leq H,W\leq500$
$1\leq P\leq H$
$1\leq Q\leq W$
$1\leq X\leq10^9$
$1\leq S_{i,j}\leq10^{12}$

考察

スライムの吸収で高橋君の強さは減少しないことから、吸収できるスライムはすべて吸収してしまってよい。

さらに、一度隣接したスライムはいつでも吸収できることを踏まえると、現時点で隣接しているスライムの中で吸収できるもののうち、最も強さの小さいものから順に吸収していくという貪欲的な方法が考えられる (証明は公式解説を参照) 。

吸収できるスライムの探索は BFS を使って行うが、 BFS の queue にはpriority_queueを採用するのがポイント。隣接マスの「スライムの強さ」、「行インデックス」、「列インデックス」を priority_queue で管理し、「スライムの強さ」で昇順ソートする。

こうすることで、毎回隣接スライムの強さを比べる必要がなくなり、計算量を改善できる。

queue の先頭要素を取得した後は、隣接している中で強さ最小のスライムを吸収できるかを判定する。もしこれが不可能な場合、高橋君はこれ以上スライムを吸収できない。

判定の条件式に注意。今回登場する数値はすべて整数型なので、単純に除算すると切り捨て処理になってうまくいかない。double型にキャストするか、天井関数などを使うこと。

この辺の処理は以前書いた記事にまとめてある。

yuulis.hatenablog.com

計算量は、priority_queueに対して各要素をpush、及びpopする処理で $O(\log HW)$ かかるので、全体としては $O(HW \log HW)$ となり、今回の制約下では十分高速。

atcoder.jp

コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

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

int main()
{
    int H, W, P, Q;
    ll X;
    cin >> H >> W >> X >> P >> Q;
    P--, Q--;
    vector<vector<ll>> S(H, vector<ll>(W));
    rep(i, 0, H) rep(j, 0, W) cin >> S[i][j];

    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> que;
    vector<vector<bool>> visited(H, vector<bool>(W, false));
    ll strength = S[P][Q];
    que.emplace(0, P, Q);
    visited[P][Q] = true;
    while (!que.empty())
    {
        auto [slime, y, x] = que.top();
        que.pop();

        if (slime >= (double)strength / X)
            break;

        strength += slime;

        rep(dir, 0, 4)
        {
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if (ny < 0 || ny >= H || nx < 0 || nx >= W || visited[ny][nx])
                continue;

            visited[ny][nx] = true;
            que.emplace(S[ny][nx], ny, nx);
        }
    }

    cout << strength << endl;
}