きままにものづくり

日々の気付いたことなんかを書いてます。

SRM635Div1Easy

問題

サイズNのdate,ratingのふたつの数列が与えられる。その中で、同じ傾きの列を持つ数列が2つ以上存在する集合の中でそれぞれの点の長さの総和が最大値を求めよ。
例) {1,2,4,8,16,32},{1,2,4,8,16,32}
傾きは{1,1,1,1,1}となる。{2,4,8,16,32},{2,4,8,16,32}が最大の長さの総和を持つ数列になる。

解法

数列の始点(i,j)を選び、下のように変数を定義する。

$dx_i = date[i+1] - date[i]$
$dy_i = rating[i+1] - rating[i]$
$dx_j = date[j+1] - date[j]$
$dy_j = rating[j+1] - rating[j]$

傾きが同じであるということは、以下を満たすfが存在することと同じである。

$dx_i = f*dx_j$
$dy_i = f*dy_j$

fに特別な制約がない場合、つまり2点ずつのみの比較だと

$dx_i * dy_j = dx_j * dy_i$

が条件となる。
3点目以降を考慮する場合は、 $f = \frac{dx_i}{dx_j}$ なので

$dx_{ik} * dx_j = dx_{jk} * dx_i$
$dy_{ik} * dx_j = dy_{jk} * dx_i$

以上のことを利用して、iとjを全探索する。

計算量

$O(N^3)$

コード