AtCoder が提供しているABC（AtCoder Beginner Contest）384 E問題をC++とPythonで解いてみました。ABC384は、2024年12月14日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Takahashi is Slime 2（Difficulty : 1002）
問題の詳細は、リンク先をご覧ください。
ABC384 E問題 Takahashi is Slime 2
優先度付きキューを用いて吸収するマスを効率的に選択します。AtCoder Problems による Difficulty は 1002 でした。
解答案
高橋くんがいるマス ＄(P, Q)$ の上下左右のマスが吸収するマスの候補になります。あるマスを吸収できたら、その上下左右のマスも吸収するマスの候補となります。
強さが小さいマスから吸収すればよいため、候補となるマスを優先度付きキューに格納すれば効率よく処理できます。
C++ プログラム例（ABC384E）
プログラムの補足です。
- すでにキューに格納されたか2次元配列
queuedで管理します。 - あるマスの上下左右をキューに格納するラムダ式
push_queueを定義します。 - ＄(P, Q)$ の上下左右のマスをキューに格納します（44行目）。
- キューからマスを取り出します。
- その強さが高橋くんの $\frac{1}{X}$ 倍以上であれば、候補となるマスが無くなるため、解を出力します 。
- 割り算の結果を
doubleで計算しました。誤差の影響を考慮してDBL_EPSILONを加えて評価しています（51行目）。
- 割り算の結果を
- その強さが $\frac{1}{X}$ 倍未満であれば、その上下左右のマスをキューに格納して、高橋くんの強さを更新します（54、55行目） 。
- その強さが高橋くんの $\frac{1}{X}$ 倍以上であれば、候補となるマスが無くなるため、解を出力します 。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, pair<int, int>> PP;
int main()
{
int h, w;
ll x;
cin >> h >> w >> x;
int p, q;
cin >> p >> q;
--p;
--q;
vector<vector<ll>> s(h, vector<ll>(w));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> s[i][j];
}
}
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
vector<vector<bool>> queued(h, vector<bool>(w, false));
priority_queue<PP, vector<PP>, greater<PP>> que;
ll result = s[p][q];
queued[p][q] = true;
auto push_queue = [&](int now_i, int now_j) -> void {
for (int d = 0; d < 4; ++d) {
int next_i = now_i + di[d];
int next_j = now_j + dj[d];
if ((0 <= next_i) && (next_i < h) && (0 <= next_j) &&
(next_j < w) && !queued[next_i][next_j]) {
que.push(
make_pair(s[next_i][next_j], (make_pair(next_i, next_j))));
queued[next_i][next_j] = true;
}
}
};
push_queue(p, q);
while (!que.empty()) {
PP now = que.top();
que.pop();
int now_i = now.second.first;
int now_j = now.second.second;
if ((double)now.first + DBL_EPSILON >= (double)result / (double)x) {
break;
}
result += now.first;
push_queue(now_i, now_j);
}
cout << result << endl;
return 0;
}高橋くんの強さとマスの強さを評価する際、整数の切り上げ結果と比較する方法も有効です。具体的には、51行目は以下のように記載します。
if (now.first >= (result + x - 1) / x) {
break;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC384E）
Python版も基本的な考え方は同じです。優先度付きキューは、heapq を使いました。以下がプログラムです。
"""AtCoder Beginner Contest 384 E"""
import heapq
def push_queue(now_i, now_j):
global h, w, di, dj, queued, que
for d in range(4):
next_i = now_i + di[d]
next_j = now_j + dj[d]
if 0 <= next_i < h and 0 <= next_j < w and not queued[next_i][next_j]:
heapq.heappush(que, (s[next_i][next_j], (next_i, next_j)))
queued[next_i][next_j] = True
h, w, x = map(int, input().split())
p, q = map(int, input().split())
p -= 1
q -= 1
s = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
s[i] = list(map(int, input().split()))
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]
queued = [[False for _ in range(w)] for _ in range(h)]
que = []
heapq.heapify(que)
result = s[p][q]
queued[p][q] = True
push_queue(p, q)
while que:
now = heapq.heappop(que)
now_i = now[1][0]
now_j = now[1][1]
if now[0] >= (result + x - 1) // x:
break
result += now[0]
push_queue(now_i, now_j)
print(result)こちらも「AC」と判定されました。
最後に
コンテスト中はBFSを用いた処理を試みましたが、WA（Wrong Answer）となりました。優先度付きキューを利用する方法は思いついたものの、時間切れとなってしまいました。勉強になりました。
引き続き ABC の問題を紹介していきます。
