F - Earn to Advance Editorial by chro4896


所持金をどこで増やすかを固定して考えると、所持金を増やすマスの間の移動は、払う費用が最少の経路を通ることが最適なのは明らかです。よって、所持金をどこで増やすかを考えることにします。
つまり、所持金を増やすマスだけを抜き出した、下のような列を考えます。ここで、\(k\) は列の長さです。

\(\displaystyle (a_{1}, b_{1}) \rightarrow (a_{2}, b_{2}) \rightarrow \cdots \rightarrow (a_{k}, b_{k})\)

ここで、問題の設定上、マス\((1,1)\) で所持金を増やすのは必須です。また、便宜上、マス\((N,N)\) も所持金を増やすマスとして扱います。
このとき、この問題は、このような列のある種の「長さ」を考えたときの最短経路問題に帰着することができます。どのように帰着するかを、この下で述べます。

\(P_{N,N}\) の値は問題の答えに影響を与えないため、以下では便宜上\(P_{N,N} = \infty\) とします。
引き続き、上に記載した列について考えます。公式解説にも記載されている通り、それまでに通過したマスの中で\(P\)が最も大きいマスで所持金を増やすことが最適です。
よって、\(1 \le i \lt k\) を満たす任意の整数\(i\) について、\(P_{a_{i},b_{i}} \lt P_{a_{i+1},b_{i+1}}\) が成り立つときだけ考えれば十分です。これにより、マス\((a_{i},b_{i})\) では、マス\((a_{i+1}, b_{i+1})\) へ移動できるだけの最低限の所持金が得られた時点で、すぐにマス\((a_{i+1}, b_{i+1})\) への移動を始めることが最適な行動になります。
これらを踏まえて、この列の「長さ」を\(2\)つの数の組\((c,r)\) で表します。この列に沿って、上に記載した最適な行動をとったときの「所持金を増やした回数」を\(c\) とし、最終的に余った金額を\(r\) とします。
この「長さ」に対し、小さい方がより最適となるような全順序を入れられれば、通常の最短経路問題と同様に、\((1,1)\) から各マスまでの列の「長さ」の最小値を順次計算していくことで解くことができます。
実は、下のような全順序\(\sqsubseteq\) を入れれば良いことがわかります。

\(\displaystyle (c, r) \sqsubseteq (c^{\prime}, r^{\prime}) \overset{\text{def}}{\Longleftrightarrow} \left( c \lt c^{\prime} \ \lor \ \left( c = c^{\prime} \ \land \ r^{\prime} \le r\right)\right)\)

これは、辞書式順序で、2番目の要素に関する順序を逆向きにしたものと言うこともできます。

あるマス\((a, b)\) へ行く経路が\(2\)つあり、それぞれ長さが\((c, r)\)\((c^{\prime}, r^{\prime})\) だったとしたとき、上で定義した全順序に従い長さを比較することで、どちらの経路が「より良い」かを判断できるか確認します。
それまでの行動回数が同じ場合、すなわち\(c = c^{\prime}\)の場合は、\(r\)\(r^{\prime}\)の大小関係で判断できることが明らかです。
次に、それまでの行動回数が異なる場合を考えるために、\(c \lt c^{\prime}\) であると仮定します。行動回数が少ない経路の場合、その分マス\((a, b)\)で所持金を\(P_{a,b}\) 増やせることを考えると、\(r^{\prime} \lt P_{a,b}\) が言えれば、長さが\((c, r)\) である経路のほうが「より良い」ことがわかります。
ここで、この「長さ」は上で述べた最適な行動をした結果であることを思い出すと、\(r^{\prime} \lt P_{a,b}\) であることがわかります。もしそうでないならば、それまでに訪れた「所持金を増やすマス」のどこかで必要以上に所持金を増やしていることになり、最適な行動をとったという仮定に矛盾するからです。

以上より、最短経路問題に帰着できました。今回の問題では右下へ行くことしかできない(DAGである)ため、左上から順次計算していくことで最短経路問題を解くことができます。以下は、この方針に従った提出です。
https://atcoder.jp/contests/abc344/submissions/51111813

posted:
last update: