\(+a, -b\) を単に \(+,-\) と書く． 操作は可換．
最適な操作列の性質
操作 \(f\) を， \(i\) に \(+\), \(j\) に \(-\) として， 操作 \(g\) を， \(j\) に \(+\), \(k\) に \(-\) とする． 操作列 \(h\) において， \(f,g\) を使うとする．
よって，任意の最適な操作列は，任意の \(i \in N\) に対して \(+,-\) の一方だけ施している．
操作 \(f\) を， \(i\) に \(+\), \(j\) に \(-\) として， 操作 \(g\) を， \(j\) に \(+\), \(k\) に \(-\) とする． 操作列 \(h\) において， \(f,g\) を使うとする．
- \(j = k\) の場合， \(f,g\) をともに使わないことにした 操作列を \(h'\) とおく．
- \(j \neq k\) の場合， \(f,g\) をともに使わないことにした上で， \(j,k\) に \(-,+\) の操作をした 操作列を \(h'\) とおく．
よって，任意の最適な操作列は，任意の \(i \in N\) に対して \(+,-\) の一方だけ施している．
判定問題
操作列 \(f\) と vector \(A\) に対して， \(A\) に \(f\) を施した vector を \(A^{f}\) と表す． \(C\)に対して \(P_{C} \in Bool\) を， 任意の\(f\) に対して \(min_{i \in N}(A^{f})_{i} \geq C\) のときにtrue と定める． \(i \in N\) を任意にとり， \(X := (A^{f})_{i}\) とおく．
よって， \(C\) 毎に \(O(N)\) で判定できる． \(C\) の取り方は binary search で\(O(log)\) ．
操作列 \(f\) と vector \(A\) に対して， \(A\) に \(f\) を施した vector を \(A^{f}\) と表す． \(C\)に対して \(P_{C} \in Bool\) を， 任意の\(f\) に対して \(min_{i \in N}(A^{f})_{i} \geq C\) のときにtrue と定める． \(i \in N\) を任意にとり， \(X := (A^{f})_{i}\) とおく．
- Case 0: \( X \geq C \) \(-\) を何回出来るかを考える． 可能な限りやっておいた方が得． \(ceil((x-c)/a)\) 回できる．
- Case : \( X < C \) \(+\) を何回できるかを考える．これは必ずやらないといけない． 最低で \(floor((c-x)/a)\) 回必要．
よって， \(C\) 毎に \(O(N)\) で判定できる． \(C\) の取り方は binary search で\(O(log)\) ．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
