コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1650 (記事作成時点)

供養

解法

$f_{k}(f_{k - 1}( \dots f_{1}(x) \dots ))$ を表す関数を $F_{k}(x)$ とすると、$F_{k}$ は3つのパラメータ $y_{k}, z_{k}, w_{k}$ を用いて以下のように表すことができる \begin{align} F_{k}(x) = \begin{cases} y_{k} + w_{k} & (x \le y_{k}) \\ x + w_{k} & (y_{k} \le x \le z_{k}) \\ z_{k} + w_{k} & (z_{k} \le x) \end{cases} \end{align}
初期状態を表すパラメータセットは $P_{0} = (y_{0}, z_{0}, w_{0}) = (- \infty, \infty, 0)$ である
$P_{i - 1}$ から $P_{i}$ は以下のように計算できる
- $t_{i} = 1$ のとき、グラフは上下に動くだけなので $P_{i} = (y_{i - 1}, z_{i - 1}, w_{i - 1} + a_{i})$
- $t_{i} = 2$ のとき、以下のように場合分けして考えることができる
  - $a_{i} \le y_{i - 1} + w_{i - 1}$ のとき、任意の $x$ について $\mathrm{max}(F_{i - 1}(x), a_{i}) = F_{i - 1}(x)$ となるので、$P_{i} = P_{i - 1}$
  - $y_{i - 1} + w_{i - 1} \le a_{i} \le z_{i - 1} + w_{i - 1}$ のとき、$x \le a_{i} - w_{i - 1}$ の区間は $\mathrm{max}(F_{i - 1}(x), a_{i}) = a_{i}$ となり、$a_{i} - w_{i - 1} \le x$ について $\mathrm{max}(F_{i - 1}(x), a_{i}) = F_{i - 1}(x)$ となるので、$P_{i} = (a_{i} - w_{i - 1}, z_{i - 1}, w_{i - 1})$
  - $z_{i - 1} + w_{i - 1} \le a_{i}$ のとき、任意の $x$ について $\mathrm{max}(F_{i - 1}(x), a_{i}) = a_{i}$ となるので、$P_{i} = (0, 0, a_{i})$
  - $a_{i} = y_{i - 1} + w_{i - 1}$ もしくは $a_{i} = z_{i - 1} + w_{i - 1}$ のときは3つの場合分けの複数に該当するが、そのいずれを採用しても $F_{k}$ の出力は同値である
- $t = 3$ のときも $t = 2$ のときと同様に考えることができる
よって、順次計算することで $P_{N}$ を得ることができる
$P_{N}$ を用いて $F_{N}(x_{i})$ を出力していけばよい