F - Earn to Advance Editorial by MMNMM
整数の組 \((i,j)\ (1\leq i,j\leq N)\) について、次のような \({{\mathbb Z} _ {\geq0}} ^ 2\) の部分集合を考えます。
- \(S _ {i,j}\coloneqq\lbrace (m,t)\in{{\mathbb Z} _ {\geq0}} ^ 2\mid{}\)高橋くんの所持金が \(m\) でマス \((i,j)\) にいるとき、ここから \(t\) 回の行動ののちマス \((N,N)\) にいることができる\(\rbrace\)
便宜上、\(S _ {N+1,j}\) や \(S _ {i,N+1}\) を \(\emptyset\) とし、\(R _ {i,N}\) や \(D _ {N,j}\) を適当な値にしておきます。 求める答えは \(S _ {0,0}\) に \((0,x)\) が含まれるような最小の \(x\) です。
\(S _ {N,N}={{\mathbb Z} _ {\geq0}} ^ 2\) です。
\(S _ {i,j}\ ((i,j)\neq(N,N))\) について、\(S _ {i+1,j},S _ {i,j+1}\) を用いて \(S _ {i,j}\) を次のように書くことができます。
\[\begin{aligned} D _ {i,j}&\coloneqq\lbrace (m+D _ {i,j},t+1)\mid (m,t)\in S _ {i+1,j}\rbrace\\ R _ {i,j}&\coloneqq\lbrace (m+R _ {i,j},t+1)\mid (m,t)\in S _ {i,j+1}\rbrace\\ \widetilde S _ {i,j}&\coloneqq D _ {i,j}\cup R _ {i,j}\\ S _ {i,j}&=\bigcup _ {n=0} ^ \infty\lbrace(m-nP _ {i,j},t+n)\mid (m,t)\in\widetilde S _ {i,j},m\geq nP _ {i,j}\rbrace \end{aligned}\]
これを使うことで、ゴールから遡りながら \(S _ {i,j}\) をすべて求めることができます。
\(S _ {i,j}\) の要素をすべて管理することはできませんが、\(S _ {i,j}\) の凸包の頂点のみを管理することで正しい答えを求めることができます。
以下、便宜上番兵として \(2\) つの点 \((\infty,2N-i-j),(0,\infty)\) を暗黙に凸包の頂点として扱うことがあります。
証明
次の \(3\) つを示します。
- \(S _ {i,j}\) の凸包と \(S _ {i,j} ^ \prime\coloneqq\bigcup _ {n=0} ^ \infty\lbrace(m-nP _ {i,j},t+n)\mid (m,t)\in(\widetilde S _ {i,j}\) の凸包\()\cap{{\mathbb Z} _ {\geq0}} ^ 2,m\geq nP _ {i,j}\rbrace\) の凸包は等しい
- \(S _ {i+1,j},S _ {i,j+1}\) の凸包が得られたとき、\(S _ {i,j}\) の凸包が求められる
- \(S _ {0,0}\) の凸包が得られたとき、答えを求められる
1.
明らかに、\(S _ {i,j}\subseteq S ^ \prime _ {i,j}\) です。 よって、これらの凸包が等しくないなら、\(S ^ \prime _ {i,j}\) の凸包の頂点 \((m,t)\) であって \(S _ {i,j}\) の凸包に含まれないものが存在します。
\((m,t)\) は、\(\widetilde S _ {i,j}\) の凸包の頂点 \((m _ 0,t _ 0)\) とある \(0\leq n\leq m/P _ {i,j}\) が存在して \((m _ 0-nP _ {i,j},t _ 0+n)\) と書けることを示します。
証明
\(S ^ \prime _ {i,j}\) の取り方から、\(\widetilde S _ {i,j}\) の凸包に含まれる点 \((m ^ \prime,t ^ \prime)\) と \(0\leq n ^ \prime\leq m ^ \prime/P _ {i,j}\) が存在して \((m ^ \prime-n ^ \prime P _ {i,j},t ^ \prime+n ^ \prime)\) です。 \(\widetilde S _ {i,j}\) の凸包の \(2\) つの隣接する頂点 \((m _ L,t _ L),(m _ R,t _ R)\) であって \(t _ L\leq t ^ \prime\lt t _ R\) であるものをとれます（\(t _ R=\infty\) の場合もあります）。 すると、線分（もしくは半直線）\((m _ L,t _ L),(m _ R,t _ R)\) 上の点 \((m _ h,t ^ \prime)\) に対して \(m _ h\leq m ^ \prime\) です。 また、線分（もしくは半直線）\((m _ L,t _ L),(m _ R,t _ R)\) 上の点 \((m _ M,t _ M)\) に対して、点 \((m _ M-n _ MP _ {i,j},t _ M+n _ M)\) であって \(t _ M+n _ M=t\) なるものが取れます。 点 \((m _ M,t _ M)\) が \((m _ L,t _ L)\) から \((m _ R,t _ R)\) へ動くとき、この点の \(y\) 座標は単調に変化するか、変化しません。 よって、\((m _ h,t ^ \prime)\) に対するこの点の \(y\) 座標と比較して、\((m _ L,t _ L)\) もしくは \((m _ R,t _ R)\) に対する \(y\) 座標の少なくとも一方はより大きくないです（\(t _ R=\infty\) のとき、\((m _ L,t _ L)\) のほうが満たすことはすぐに示されます）。
よって、\(m ^ \prime-n ^ \prime P _ {i,j}\geq m _ 0-nP _ {i,j}\) かつ \(t ^ \prime+n ^ \prime=t _ 0+n\) となるような凸包の頂点 \((m _ 0,t _ 0)\) と \(n\) が存在します。 \((m,t)\) が凸包の頂点であることから、\(m ^ \prime-n ^ \prime P _ {i,j}=m _ 0-nP _ {i,j}\) でなければならず、示されました。
よって、\((m,t)\) は \(\widetilde S _ {i,j}\) に含まれる点 \((m _ 0,t _ 0)\) と \(0\leq n\leq m/P _ {i,j}\) について \((m _ 0-nP _ {i,j},t _ 0+n)\) と書けますが、これは \(S _ {i,j}\) に含まれます。
よって、\(S _ {i,j}\) と \(\widetilde S _ {i,j}\) の凸包は等しいです。
2.
\(S _ {i,j}\) の凸包を、\(S _ {i+1,j},S _ {i,j+1}\) それぞれの凸包から正しく求められることを示します。
\(D _ {i,j},R _ {i,j}\) の凸包は \(S _ {i+1,j},S _ {i,j+1}\) の凸包を平行移動したものなので、\(O(\) 凸包の頂点数 \()\) で求められます。
\(\widetilde S _ {i,j}\) の凸包は \(D _ {i,j},R _ {i,j}\) の凸包の頂点から \(O(\) 凸包の頂点数の合計 \()\) で求められます。
\(\widetilde S _ {i,j}\) の凸包の頂点 \((m,t)\) のうち、\(m+tP _ {i,j}\) が最小のもの \((m _ {\min}, t _ {\min})\) をとると、\(S _ {i,j}\) の凸包は \(\widetilde S _ {i,j}\) の凸包の頂点 \((m,t)\) のうち \(t\leq t _ {\min}\) であるものと、\(\left\lbrace\left(m _ {\min}\bmod P _ {i,j},t _ {\min}+\left\lfloor\dfrac{m _ {\min}}{P _ {i,j}}\right\rfloor\right),\left(0,t _ {\min}+\left\lceil\dfrac{m _ {\min}}{P _ {i,j}}\right\rceil\right)\right\rbrace\) と \((0,\infty)\) からなります。
これも \(O(\widetilde S _ {i,j}\) の凸包の頂点数 \()\) で求められます.
3.
\(S _ {0,0}\) の凸包の頂点 \((m,t)\) のうち \(m=0\) であるものは、\(S _ {0,0}\) に含まれる \((0,t)\) のうち \(t\) が最小のものなので、求められます。
例えば、以下の図のように管理を行うことになります。
凸包の頂点数はたかだか \(O(N ^ 2)\) 個になることが示せます。
証明
集合 \(T _ {i,j}\coloneqq\lbrace t+i+j\mid (m,t)\) は \(S _ {i,j}\) の凸包の頂点 \(\rbrace\) を考えると、\(T _ {i,j}\) は \(T _ {i+1,j}\cup T _ {i,j+1}\) から \(0\) 個以上要素を削除し、たかだか \(2\) つ要素を付け足したものであることがわかります。 \(T _ {i,j}\) で付け足されたものを \(\lbrace x _ {i,j,0},x _ {i,j,1}\rbrace\) とすると、\[T _ {i,j}\subseteq \bigcup _ {i\leq i ^ \prime,j\leq j ^ \prime}\lbrace x _ {i ^ \prime,j ^ \prime,0},x _ {i ^ \prime,j ^ \prime,1}\rbrace\]
となるので、たかだか \(2N ^ 2\) 個です。
実装例は以下のようになります。 計算中の値が \(64\operatorname{bit}\) 整数に収まらない場合があります。
#include <iostream>
#include <vector>
#include <ranges>
#include <utility>
#include <optional>
int main() {
using namespace std;
using bigint = __int128;
constexpr bigint inf = bigint{1} << 100;
unsigned N;
cin >> N;
vector P(N, vector<unsigned>(N)), R(N, vector<unsigned>(N)), D(N, vector<unsigned>(N));
for (auto &&v : P)
for (auto &&p : v)
cin >> p;
for (auto &&v : R)
for (auto &&r : v | views::take(N - 1))
cin >> r;
for (auto &&v : D | views::take(N - 1))
for (auto &&d : v)
cin >> d;
vector<vector<pair<bigint, bigint>>> dp(N + 1);
dp[N - 1].emplace_back(0, 0);
// p1, p2, p3 の 3 点ともに凸包に必要なら true を返す
const auto check{[](const auto &p1, const auto &p2, const auto &p3) {
const auto&[a, b]{p1};
const auto&[c, d]{p2};
const auto&[e, f]{p3};
return a * d + c * f + e * b < a * f + c * b + e * d;
}};
// 点列 convex_hull (型は vector<pair>) のそれぞれの点を +(cost, 1) だけした列を作る
// 呼び出すたびに点を先頭から返す関数オブジェクトを返す
const auto shift_yield{[](const vector<pair<bigint, bigint>>& convex_hull, unsigned cost){
return [&convex_hull, cost, it{begin(convex_hull)}]() mutable -> optional<pair<bigint, bigint>> {
if (it == end(convex_hull))
return nullopt;
auto [money, turn]{*it};
++it;
return make_pair(money + cost, turn + 1);
};
}};
// ソートされた点列を 2 つとり、マージした点列を作る
// 呼び出すたびに点を先頭から返す関数オブジェクトで点列を表す
const auto merge_seqs{[](auto&& seq1, auto&& seq2){
return [&seq1, &seq2, front1{seq1()}, front2{seq2()}]() mutable -> optional<pair<bigint, bigint>> {
if(!front1 || (front2 && front1->first < front2->first))
return exchange(front2, seq2());
return exchange(front1, seq1());
};
}};
for(unsigned i{N}; i--; ){
for(unsigned j{N}; j--; ){
vector<pair<bigint, bigint>> bottom;
swap(bottom, dp[j]); // 旧 dp[j] を bottom とし、更新を行う
const auto p{P[i][j]};
// このマスでの最適な行動を持っておく
bigint earn_here{inf};
unsigned earn_index{};
// 点列を作る
optional<pair<bigint, bigint>> now;
auto D_seq{shift_yield(bottom, D[i][j])}; // 下のマスへ移動するときの凸包
auto R_seq{shift_yield(dp[j + 1], R[i][j])}; // 右のマスへ移動するときの凸包
auto candidate_points{merge_seqs(D_seq, R_seq)}; // マージした列
while (now = candidate_points()) { // マージした列から点を取り出して
// 凸包を作る
while (size(dp[j]) > 1 && !check(dp[j][size(dp[j]) - 2], dp[j].back(), *now))
dp[j].pop_back();
dp[j].emplace_back(*now);
// 0 から稼ぐときの最適を更新
if (earn_here > now->first + now->second * p) {
earn_here = now->first + now->second * p;
earn_index = size(dp[j]);
}
}
// 0 から稼いだほうがいい部分を消す
dp[j].erase(begin(dp[j]) + earn_index, end(dp[j]));
// 端数と 0 の点を追加
if (dp[j].back().first > 1 && earn_here % p) dp[j].emplace_back(earn_here % p, earn_here / p);
if (dp[j].back().first) dp[j].emplace_back(0, (earn_here + p - 1) / p);
}
}
cout << static_cast<unsigned long>(dp.front().back().second) - 1 << endl;
return 0;
}
posted:
last update: