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

标签：

• Tokyo-University
• Isotonic-Regression-and-Pool-Adjacent-Violators

Author

hari64boli64

Description

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

$$\sum_{i=1}^n (A[i] - B[i])^2$$

を最小にする長さ $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$ の近似配列を求める多項式時間アルゴリズムを与えよ。ただし、有理数どうしの四則演算は定数時間で行えるものと仮定してよい。

题目描述

考虑元素均为有理数的数组。对长度为 $n$ 的数组 $A$，把使

$$\sum_{i=1}^n(A[i]-B[i])^2$$

最小的单调非降数组 $B[1]\le B[2]\le\cdots\le B[n]$ 称为 $A$ 的近似数组。

1. 在 $A$ 末尾追加一个元素得到 $A'$，即 $A'[i]=A[i]$（$1\le i\le n$）。设 $B,B'$ 分别为 $A,A'$ 的近似数组。
   1. 若 $A'[n+1]\ge B[n]$，证明
      B'[n+1]=A'[n+1].$$
   2. 若 $B[1]=\cdots=B[n]$ 且 $A'[n+1]<B[n]$，证明 $B'[1]=\cdots=B'[n+1]<B[n],$ 并求这个公共值。
2. 给出求任意数组 $A$ 的近似数组的多项式时间算法。可假设有理数四则运算耗时为常数。

考点

• 保序回归：在单调约束下最小化平方误差。
• 凸二次优化：利用区块均值刻画最优解并证明唯一性。
• 相邻违例合并算法：当相邻区块均值违反单调性时反复合并并重算均值。
• 增量构造与复杂度：逐个追加数据、维护分块结构，给出多项式时间界。

Kai

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

$$\begin{aligned} A & =[0,-1,0,1,0] \\ B_1 & =[-1,-1,0,1,1] \\ B_2 & =[0,0,0,0,0] \\ (A' & =A+[100]) \end{aligned}$$

などとすると、近似配列に一意性は無いことが分かるが、そのようなことが(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)$ とすると、

$$\begin{aligned} \sum_{i=1}^{n}{(A[i]-b)^2} = \sum_{i=1}^{n}{A[i]^2} -2b \sum_{i=1}^{n}{A[i]} + nb^2 \end{aligned}$$

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

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