AtCoder Regular Contest (ARC) 056 D - サケノミ についての記事です．

問題へのリンク

状況

解けないだけではなく，答を見てもなかなかわからなかったので，整理するために書いています．下記を参考にしています．

解法

時刻 $2j+1$ にドリンクを飲むような飲み方全部に関する，時刻 $2j+1$ 時点での美味しさの総和の最大値を $x(j)$ とする． 時刻 $2i$ に全部のグラスが空だったとき，半開区間 $(2i, 2j]$ に属する時刻に注がれるドリンクの美味しさの総和を $y(i, j)$ とすると， $x(j) = \max \{ x(i) + y(i, j) \mid i < j \} $ である．ここで，$z(i, j) = x(i) + y(i, j)$ と書くことにする．時刻 $j$ に注がれるドリンク全体の集合を $P$ とし，$ p \in P $ に対して時刻 $2j$ の一回前にドリンク $p$ が注がれる時刻を $l_p$ とする (時刻 j が初回なら，$l_p = 0$ とする)．すると，次が成り立つ．

  • $x(j) = z(j,j) = \max \{ z(i,j) \mid i < j \}$
  • $z(i,j) - z(i, j-1) = \sum \{ w_p \mid p \in P,; i \in [l_p, j) \}$

したがって，ベクトル $ v_j = ( z(i,j) \mid i < j ) $ を $j$ に関して遅延伝搬セグメント木 (区間和，区間最大値) で更新していくことができ，$O(M \log M)$ (ここに $M = \sum \{ M_i \mid i \leq N \}$ )で計算できる．答は最終時刻 $T$ に対する $x(T) = z(T, T)$ である．

その他

似たような問題を見たことがあるような気がして探してみると，EDPC の W. Intervals とほぼ同じでした．こちらの方が古いですが．何度やっても解けません．