E - Takahashi is Slime 2 Editorial
by
MMNMM
一度接したスライムは吸収しない限り接し続けることと、高橋くんの強さが減少することはないことから、吸収できるスライムはすべて吸収してしまって損しません。
ここから、次のようなアルゴリズムが考えられます。
- 以下の行動を繰り返せるだけ繰り返す。
- 接しているスライムのうち、最も強さの小さいスライムを吸収する
最適性の証明
このアルゴリズムで吸収したスライムの集合を \(S\) とし、\(S\neq S ^ {\prime}\) なるスライムの集合 \(S ^ {\prime}\) を吸収したほうが最終的な強さが大きいとします。
このとき、\(S ^ {\prime}\) を吸収する行動の列をひとつ固定し、その列ではじめて吸収される \(a\in S ^ {\prime},a\notin S\) を満たすスライム \(a\) について考えます。 すると、上のアルゴリズムで \(S\) の要素をすべて吸収したときには \(a\) に接しており、かつその時点での高橋くんの強さは \(a\) を吸収するのに十分であることが言えます。
これは \(a\notin S\) に反するため、\(S\) が最適であることがわかります。\(\square\)
あとは、これを実現する十分高速なアルゴリズムを実装すればよいです。
スライムをひとつ吸収するごとに、接しているスライムの個数はたかだか \(2\) つ増えます(ひとつ減り、たかだか \(3\) つのスライムと新しく接します)。 行動を行おうとするたびに接しているスライムをすべて確認していては実行時間制限に間に合わせるのは難しいですが、接しているスライムの大きさを優先度付きキューや平衡二分探索木などで管理することでこれを行動一回あたり \(O(\log HW)\) 時間とすることができます。
行動回数はたかだか \(HW\) 回なので、十分高速です。
実装例は以下のようになります。
#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;
// 周囲に大きすぎて吸収できないスライムを番兵として配置しておく
// 500 × 500 × 10^12 = 2.5 × 10^19 あれば十分
vector slime_size(H + 2, vector(W + 2, 250000000000000000UL));
// 中央 H × W マスだけ読み込む
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 (size >= (now_size + X - 1) / X)
break;
// スライムを吸収する
now_size += size;
// 新たに接したスライムを優先度付きキューに追加する
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: