CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358) G問題メモ

CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358)

いつもよりF,Gが簡単め?（面倒くささは除いて）

G - AtCoder Tour

• $H$ 行 $W$ 列のグリッドの各マスに、整数 $A_{i,j}$ が書かれている
• 高橋君ははじめマス $(S_i, S_j)$ におり、以下の行動を $K$ 回繰り返します。
  • 高橋君は現在いるマスに留まるか、上下左右に連接したマスに移動する。その後の時点で高橋君がいるマスを $(i, j)$ として $A_{i, j}$ の楽しさを得る。
• 高橋君が得ることのできる楽しさの合計の最大値を求めてください。

• $1 \leq H, W \leq 50$
• $1 \leq K \leq 10^9$
• $1 \leq S_i \leq H$
• $1 \leq S_j \leq W$
• $1 \leq A_{i, j} \leq 10^9$

最適な行動は、「始点からどこかのマスへ辿り着く」→「辿り着いたら、そこに留まり続ける」となる。

留まるマスを $T$ とする。$T$ は、$S$ から $T$ に行くのに経由したマスの中で、$A_{i,j}$ が単独最大のマスであるとしてよい。
（$T$ の他に最大マスがある場合、代わりにそこで留まり続けて損しない）

また、$S$ から $T$ に行く過程の途中で留まったり、同じマスを2度通ったりする必要も無い。（その分、速く $T$ に着いて留まる回数を多くした方がいい）

当然、$A_{i,j}$ が大きいマスを $T$ とした方がよいが、 遠くにはるばる行くより近場のマスを選んだ方が $K$ によっては最善となることもある。

S 9 1 ...  1    10に辿り着くために1の海をはるばる泳ぐより、
1 1 1      1    9で留まった方がよいこともある。
:          :
1 1 1 ... 10

また、途中の経路も、速く着いた方が長く $T$ に留まれるが、 少し迂回して $A_{i,j}$ が大きいマスを経由した方がよい場合もある。

 S 9 9  最短で下に行くより 9 を拾っていった方がいい
 1 1 9
10 9 9

このために、$S$ から単なるコストや移動回数を持った経路探索をしても、上手く最適を求められない。

制約から $O(H^2W^2)$ が間に合いそうなので、 「$T$ を全探索」→「$T$ を固定した条件でグリッド探索」してもよい、ということになる。

$T$ マスに書かれた値を $A_T$ とする。
仮に「$K$ 回全てで $A_T$ を得られた」とすると総計は $KA_T$ で、これをまず貰っておく。
実際には辿り着くまでに踏む各マス $(i,j)$ に対し、$A_T-A_{i,j}$ だけ減少する。

これをコストとして、$S$ から $T$ までDijkstraをすると、$T$ を固定した場合の答えが求まる。
前述の通り、探索するマスは $A_{i,j} \lt A_T$ であるマスのみとしてよいので、コストは常に非負である。

Python3

from heapq import heappop, heappush

h, w, k = map(int, input().split())
si, sj = map(int, input().split())
field = [-1] * (w + 2)
for _ in range(h):
    field.append(-1)
    field.extend(map(int, input().split()))
    field.append(-1)
field.extend([-1] * (w + 2))
s = si * (w + 2) + sj
hw = (h + 2) * (w + 2)

INF = 1 << 60
ans = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        t = i * (w + 2) + j
        ft = field[t]

        dp = [INF] * hw
        dp[s] = 0
        q = [(0, s)]
        while q:
            cost, u = heappop(q)
            if u == t:
                break
            if dp[u] < cost:
                continue
            for di in (-w - 2, -1, 1, w + 2):
                v = u + di
                if field[v] == -1 or (v != t and field[v] >= ft):
                    continue
                cv = cost + ft - field[v]
                if dp[v] <= cv:
                    continue
                dp[v] = cv
                heappush(q, (cv, v))
        tmp = ft * k - dp[t]
        ans = max(ans, tmp)

print(ans)

どこに $T$ を設定しようと、また、$S$ からどんなルートを辿ろうと、$HW$ 回以内には必ず、最適なルートで $T$ に辿り着いている。

• $\mathrm{DP}[i,j,k]=$ マス $(i,j)$ に、$k$ 回で辿り着くまでの最大嬉しさ

として、$k \le HW ( \le 2500)$ までの範囲を探索すれば、それぞれの状況からさらに $(i,j)$ に $K-k$ 回留まり続けた中での最大値が答えとなる。

同じマスを2回経由するルートなども探索されてしまうが、考え方はシンプルになる。