[1] 最適解の構造

\(A\) が昇順ソートされているとします。また、対称性より \(B_1 = A_1\) として良いです。

目的値を最小化する \(B\) のうち少なくとも \(1\) つは、以下の条件を満たします。

\(k\) を \(B_k = A_N\) となる添字とする。このとき、\(B_1\lt B_2\lt\cdots \lt B_k,~B_k\gt B_{k+1}\gt\cdots\gt B_N\) が成立する。

最適解が \(B_k\gt B_{k+1}\gt\cdots\gt B_N\) を満たさないとします。このとき、\(B_{k+1},\cdots,B_{N}\) を降順ソートすると目的値が真に小さくなるので、\(B\) の最適性に反します。従って、全ての最適解が \(B_k\gt B_{k+1}\gt\cdots\gt B_N\) を満たします。

最適解が \(B_1\lt B_2\lt\cdots \lt B_k\) を満たさないとします。すると、ある \(2\leq i\leq k-2\) が存在して \(B_i > B_{i+1}\) を満たします。このとき、\(B_i\) を \(B_k\) より末尾側に、\(B_k\) 以降が単調減少となるように移動しても目的値は増加しません。この操作を何回か繰り返すことによって、目的値を増加させずに \(1\) から \(A_N\) までの部分を単調増加にすることができます。

以上より、主張が示されました。

---

[2] 動的計画法

上述の条件を満たす \(B\) について、目的値は \(\displaystyle\sum_{i=1}^{k-1}\left\lfloor\frac{B_{i+1}}{B_i}\right\rfloor\) となります。従って、問題を次のように言い換えることができます。

頂点 \(1,\dots,N\) からなる有向グラフがあり、\(1\leq i \lt j\leq N\) を満たす \((i,j)\) について \(i\) から \(j\) への重み \(\displaystyle w(i,j)\coloneqq\left\lfloor\frac{A_j}{A_i}\right\rfloor\) の辺が貼られている。このとき、頂点 \(1\) から頂点 \(N\) への最短パスの重みを求めよ。

以降ではこの問題を考えます。グラフは DAG なので、以下のような dp を考えることができます。

\(\displaystyle\mathrm{dp}(i)\coloneqq\) 頂点 \(0\) から頂点 \(i\) への最短パスの重み

dp の初期化は \(\mathrm{dp}(1) = 0\) で、求めたい答えは \(\mathrm{dp}(N)\) です。この dp は、以下のように計算できます。

\[ \mathrm{dp}(i) = \min\left\lbrace \mathrm{dp}(j) + w(j,i) ~\middle | ~ 1\leq j \lt i \right\rbrace \]

---

[3] 遷移先の限定

このままだと dp の計算量は \(\Theta(N^2)\) となってしまいますが、実は遷移先を高々 \(2\) つに絞ることができます。\(i\) からの遷移として重みが同じ辺が複数あれば、その中で添字が最大の遷移先のみを考慮すればよいことに注意してください。

\(i\) からの遷移先として考えるべきものは、具体的には以下の \(2\) つです。

• \(w(i,j) = 1\) を満たす \(j\) があるとき、そのような \(j\) の中で最大のもの
• \(w(i,j)\geq 2\) を満たす \(j\) があるとき、そのような \(j\) の中で最小のものを \(k\) とする。このとき、\(w(i,j) = w(i,k)\) となる \(j\) の中で最大のもの

二分探索を用いることによって、この \(2\) つの遷移先はいずれも \(O(\log N)\) 時間で計算することができます。よって、全体の計算量は最初のソートを合わせて \(O(N\log N)\) です。

---

[4] 証明

遷移先としてこの \(2\) つのみを考慮すればよいことを確認していきましょう。

まず、\(2\) つ目の候補が存在しないときは \(w(i,N) = 1\) なので、直接 \(N\) (\(1\) つ目の候補) に遷移するのが最適です。

次に、\(2\) つ目の候補が存在する場合を考えます。この候補を \(j\) とします。「同じ重みの辺で、それよりも添字が大きい遷移先はない」という意味で可能な遷移先であって、\(2\) つの候補のいずれにも当てはまらないものとして、任意に \(k\) を取ります。すると、候補の決め方より \(k > j\) です。さらに、\(w(i,j) + w(j,k)\leq w(i,k)\) となることを示します。これが成立すれば、\(i\) から \(j\) より後ろへの直接の遷移を考慮しなくていいことがわかります。

\(j\) の取り方より、\(2\leq w(i,j)\lt w(i,k)\) です。また、\(A_j\geq w(i,j)A_i,~ A_k \lt (w(i,k) + 1)A_i\) なので、\(\displaystyle\frac{A_k}{A_j} < \frac{w(i,k) + 1}{w(i,j)}\) が従います。\(w(i,j),w(i,k)\) はいずれも整数なので、両辺の floor を考えることで \(\displaystyle w(j,k)\leq \frac{w(i,k)}{w(i,j)}\) となります。さらに、\(w(i,j)\) は整数なので \(\displaystyle w(j,k)\leq \left\lfloor\frac{w(i,k)}{w(i,j)}\right\rfloor\) です。

ここまでで、\(\displaystyle w(i,j) + w(j,k)\leq w(i,j) + \left\lfloor\frac{w(i,k)}{w(i,j)}\right\rfloor\) が示せました。最後に、右辺が \(w(i,k)\) 以下であることを示して証明を完成させます。\(\displaystyle \left\lfloor\frac{w(i,k)}{w(i,j)}\right\rfloor = 1\) の場合は \(w(i,j)\lt w(i,k)\) より主張が従います。\(\displaystyle \left\lfloor\frac{w(i,k)}{w(i,j)}\right\rfloor\geq 2\) の場合は、\(w(i,j)\geq 2\) と合わせて \(\displaystyle w(i,j) + \left\lfloor\frac{w(i,k)}{w(i,j)}\right\rfloor \leq w(i,j)\cdot \left\lfloor\frac{w(i,k)}{w(i,j)}\right\rfloor\leq w(i,k)\) です。よって、いずれの場合も主張が示されました。