東京大学 情報理工学研究科 数理情報学 2020年度 第5問
Author
Description
各要素が有理数の配列を考える。配列 \(A\) の第 \(i\) 番目の要素を \(A[i]\) で表す。長さ \(n\) の配列 \(A\) に対し、
を最小にする長さ \(n\) の単調非減少配列 \(B\) を、\(A\) の近似配列と定義する。 ただし、\(B\) が単調非減少とは、\(B[1] \leq B[2] \leq \cdots \leq B[n]\) を満たすこととする。 以下の設問に答えよ。
(1) 長さ \(n\) の配列 \(A\) の末尾に要素を1つ追加した配列を \(A'\) とする。つまり \(A'[i]=A[i] \ (1 \leq i \leq n)\) が成り立つ。また、\(B, B'\) をそれぞれ \(A, A'\) の近似配列とする。
- (1-1) \(A'[n+1] \geq B[n]\) ならば、\(B'[i]=B[i] \ (1 \leq i \leq n)\) かつ \(B'[n+1]=A'[n+1]\) であることを示せ。
- (1-2) \(B[1]=B[2]=\cdots =B[n]\) かつ \(A'[n+1] < B[n]\) とする。このとき \(B'[1] = B'[2] = \cdots = B'[n+1]\) かつ \(B'[n+1] < B[n]\) であることを示し、\(B'[n+1]\) を求めよ。
(2) 配列 \(A\) の近似配列を求める多項式時間アルゴリズムを与えよ。ただし、有理数どうしの四則演算は定数時間で行えるものと仮定してよい。
Kai
まず、これは問題に誤りがあると思われる。例えば
などとすると、近似配列に一意性は無いことが分かるが、そのようなことが(1-1)では考慮されていない様に見受けられる。
以下、この議論は省略する。
(1)
(1-1)
\(B'[n+1] \neq A'[n+1]\) を仮定し、大小関係で場合分けをする。
- \(B'[n+1] < A'[n+1]\) のとき、\(n\) 番目以下に関して、実行可能領域が狭まるので、解は悪化する。\(n+1\) 番目に関しても悪化。よって、全体で悪化しており、これは最適解にはならない。
- \(B'[n+1] > A'[n+1]\) のとき、\(B'[n+1]>B[n]\) より、\(B'[n+1]\) の値を小さくすれば改善される。よって、これは最適解にはならない。
(1-2)
(注意:この問題は、見かけよりも難しいはずです。 対策会ではこの問題の厳密性を持った解答が出なかったらしいです)
問題で与えられている近似配列について、\(B[i]=b\) と置く。
\(B'[n+1]<B[n]\) を以下では仮定する。
\(B[1]=b_1\) という変数についてのみの制約付き最適化問題を考える。 この時、\(\min_{b_1\leq b}(A[1]-b_1)^2\) という制約付き最適化問題を考えると、近似配列において \(B[1]=b\) であることから、この部分問題においても \(b_1=b\) が最適解であると分かる。 特に、目的関数が凸であるため、\(b_1 \leq b\) 全体において、\(+\) に変化させる方が目的関数の値を減少させると分かる。
いま、\(B'[1]=b'_1\) に関して、\(\min_{b'_1 \leq B'[2] (\leq b)}(A[1]-b'_1)^2\) という部分的な制約付き最適化問題を考えると、先の議論より、\(b'_1=B'[1]=B'[2]\) が最適解である。
続いて、同様に、\(B[1]=B[2]=b_2\) についても、部分的な制約付き最適化問題を考える。
近似配列の形から、また、\(\sum_{i=1}^{2}(A[i]-b_2)^2\) が凸であることから、同様の議論が行え、\(B'[1]=B'[2]=b'_2\) に関して、\(\min_{b'_2\leq B'[3](\leq b)}\sum_{i=1}^{2}(A[i]-b'_2)^2\) の最適解は \(b'_2=B'[1]=B'[2]=B'[3]\) である。
以下、帰納的に考えると、\(B'[1]=B'[2]=\cdots=B'[n]=B'[n+1]\) が言える。
あとは、この条件の元での最適解が以下で示す形であることから、前半の題意は直ちに従う。
\(B'[i]=b \; (\forall i)\) とすると、
よって、\(b=\frac{1}{n}\sum_{i=1}^{n}{A[i]}\) が最適解。
(2)
DP をする。
\(k\) 番目までの近似配列がそれぞれ一つ求まっているとする。
- \(A[k+1] \geq B[k]\)、(1-1)より、\(B[k+1]=A[k+1]\) で最適
- \(A[k+1] < B[k]\)、\(B[k]-B[i] \; (\forall 1 \leq i \leq k)\) だけ、全体(つまり、\(A\) も \(B\) も)をずらすと、(1-2) に帰着される。よって、近似配列が定まる。(記述は難しい。ここがある意味本質だと思うが、図を書いた方が分かりやすいので、ここでは省略する。ある人に対して説明した際には、「顔を傾ける」という表現をした。その方が意味として本質的かも知れない)
これは明らかに多項式時間で求まる。