Codeforces Round #642 (Div. 3) - F. Decreasing Heights - Senの競技プログラミング備忘録

概要

H*Wの盤面が存在していて、それぞれのマス(i, j)ごとにはa[i][j]という高さがある。
Senくんははじめ(1,1)にいて、(H, W)まで行きたい。(i, j)にいるとき、次に行ける場所は(i+1, j)と(i, j+1)のうち、高さが(i, j)よりちょうど1だけ高い場所である。
実際に行く前に、ナマズに頼んで任意のマス目の高さを1だけ減らすことができる。これによって1円かかる。高さが負になってもよい。
少なくとも1つのルートで(1,1)から(H,W)に行けるようにするためには最低何円かかるか？

制約：　1 <= H, W <= 100, 1 <= a[i][j] <= 10^15

ACするまで

1. それぞれのマスに(1,1)からの距離を補正した値を考えると、いくつかのマスは自身自体の高さを減らさない限り採用できなさそう。
2. ある経路を考えると、(1,1)の高さをどこまで減らすべきか？という問題は簡単な証明する。
3. 基準となる高さがどこかを持ちながらDP->遷移が重そう・・・ $O(H^3 W^3)$ になりそう
4. 逆に考えるんだ・・・最小値を決めてDPで経路を見たらいいと・・・・
5. AC!

考察

配列は0-idx、マス目番号は1-idx。

b[i][j]=a[i][j] - i - jとする。このように距離で補正したb[i][j]によって、a[0][0]の高さをpとしたときに経路上のコストは次の式で表せる。(このb[i][j]を使うことで、各所での高さを(1,1)の高さに換算できる。)ここで、p>b[i][j]ならば、(1,1)を高さpにして通れないということである。
$\sum_{(i,j)∈通るマス}^{} b_{ij}-p$
これの最小化をするとき、p<=b[i][j]という条件から、 $p=\min(経路上のb_{ij})$ にするべきであるとわかる。

さて、どうやって最小を持ちながらDPするのだろうか？

dp[i][j][k][l] := (i,j)まで行って、最小値を(k, l)にしたときの最小コスト

として考えてみる。しかし、遷移を配るDPでやってももらうDPでやっても[k][l]の部分で遷移に $O(HW)$ かかりそう・・・(たぶんできるけどつらい)

しかし、ここで「最適なルートにおける基準となるb[i][j]を全部試せばよくない？」

$O(HW)$ でpにするb[i][j]を全探索して、それぞれの条件下で(i, j)を必ず通るような経路での最小コストを計算すればよい！

(i, j)を必ず通る経路を計算するときに、以下のコードのように実装するとわかりやすい。

//必ず通るマスを(mi, mj)とする。
for(int i = 0; i < mi; i++)for(int j = 0; j < mj; j++){
dp[i + 1][j] = ...
dp[i][j + 1] = ...
}

for(int i = mi; i < H; i++)for(int j = mj; j < W; j++){
dp[i + 1][j] = ...
dp[i][j + 1] = ...
}

ACソースコード：
Submission #80910480 - Codeforces

最後に

大学B2になってから課題が多い。消化に移管がかかってなかなかかけないし競プロもできてない。