東京大学情報理工学研究科数理情報学 2019年8月実施第5問

Author

各要素が有理数の配列を考える。配列の第番目の要素をで表す。長さの配列に対し、

を最小にする長さの単調非減少配列を、の近似配列と定義する。ただし、が単調非減少とは、を満たすこととする。以下の設問に答えよ。

(1) 長さの配列の末尾に要素を1つ追加した配列をとする。つまりが成り立つ。また、をそれぞれの近似配列とする。

(2) 配列の近似配列を求める多項式時間アルゴリズムを与えよ。ただし、有理数どうしの四則演算は定数時間で行えるものと仮定してよい。

まず、これは問題に誤りがあると思われる。例えば

などとすると、近似配列に一意性は無いことが分かるが、そのようなことが(1-1)では考慮されていない様に見受けられる。

以下、この議論は省略する。

を仮定し、大小関係で場合分けをする。

(注意:この問題は、見かけよりも難しいはずです。対策会ではこの問題の厳密性を持った解答が出なかったらしいです)

問題で与えられている近似配列について、と置く。

を以下では仮定する。

という変数についてのみの制約付き最適化問題を考える。この時、という制約付き最適化問題を考えると、近似配列においてであることから、この部分問題においてもが最適解であると分かる。特に、目的関数が凸であるため、全体において、に変化させる方が目的関数の値を減少させると分かる。

いま、に関して、という部分的な制約付き最適化問題を考えると、先の議論より、が最適解である。

続いて、同様に、についても、部分的な制約付き最適化問題を考える。

近似配列の形から、また、が凸であることから、同様の議論が行え、に関して、の最適解はである。

以下、帰納的に考えると、が言える。

あとは、この条件の元での最適解が以下で示す形であることから、前半の題意は直ちに従う。

とすると、

よって、が最適解。

DP をする。

番目までの近似配列がそれぞれ一つ求まっているとする。

、(1-1)より、で最適
、だけ、全体(つまり、もも)をずらすと、(1-2) に帰着される。よって、近似配列が定まる。(記述は難しい。ここがある意味本質だと思うが、図を書いた方が分かりやすいので、ここでは省略する。ある人に対して説明した際には、「顔を傾ける」という表現をした。その方が意味として本質的かも知れない)

これは明らかに多項式時間で求まる。