問題
各成分が0以上の成分であるa[i](1<=i<=N)を以下の条件を満たすように定めたい。1. | a[i] - a[i+1] | <= K
2. a[x[i]] <= t[i]
取りうる数列の最大値を求めよ.
ただし
N<=10^9くらい
size(x) = size(t) <= min(500,N)
解法
xとtのサイズが小さいのでa[x[i]]から傾きKの直線を弾いて交差するものを縮め、それを逆向きにもやって更新がなくなるまで続けた後に最大の高さを求めるみたいなことをやる。
理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます.
凸解析のツールの一つとして凸共役という概念があります. $I\subseteq \mathbb{R}$上で定義された実関数$f$の凸共役とは \[ f^*(a) = \sup_{x\in I}\{ax - f(x)\} \] で定義されます. 通常は$I=\mathbb{R}$...
0 件のコメント:
コメントを投稿