K - Exhibition 3 Editorial by KoD
5 / 13 / 2022 追記 : 解答例に間違いがあったため修正しました。また、計算量を \(O(N \log \max V_i) \rightarrow O(N \log (N\max V_i))\) に修正しました。
ちょうど \(m\) 個の絵画を残すときの価値の総和の最大値を \(f(m)\) とおきます。\(f\) は上に凸であることを示します。
\(k-1\) 個残すときの最大値を達成する絵画の添字の列を \(a_1, \dots, a_{k - 1}\) とおき、\(k+1\) 個残すときの最大値を達成する絵画の添字の列を \(b_1, \dots, b_{k + 1}\) とおきます。これらをマージして得られる列を \(c_1 \dots, c_{2k}\) とおくと、\(c_1, c_3, \dots, c_{2k-1}\) を選ぶ方法および \(c_2, c_4, \dots, c_{2k}\) を選ぶ方法はいずれも問題文の条件を満たします。これは以下の考察からわかります。
- \(X_{c_{i + 1}} - X_{c_{i - 1}} \lt D\) であるとき、\(X_{c_{i + 1}} - X_{c_{i}} \lt D\) かつ \(X_{c_{i}} - X_{c_{i - 1}} \lt D\) が成り立つが、\(c_{i - 1}, c_{i}, c_{i+ 1}\) にはともに \(a\) 由来あるいはともに \(b\) 由来の \(2\) 要素が存在するので、\(a, b\) が条件を満たす選び方であることに反する。
よって、\(c_1, c_3, \dots, c_{2k-1}\) を選ぶ場合と \(c_2, c_4, \dots, c_{2k}\) を選ぶ場合の価値の最大値の大きい方を \(S\) とおくと \(S \geq \frac{f(k - 1) + f(k+1)}{2}\) が成り立ちます。よって、\(f\) が上に凸であることが示されました。
凸性を用いると、Aliens DP あるいは WQS Binary Search と呼ばれるテクニックを用いることでこの問題を解くことができます。絵画の個数制約を取り払う代わりに \(1\) つの絵画を残すたびに \(\lambda\) のコストを支払うとした問題は \(O(N)\) で解くことができるので、全体の計算量は \(O(N \log (N\max V_i))\) となります。
参考文献 :
posted:
last update: