Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 285 E問題 Work or Rest

AtCoder ABC285 ABC E問題 500 pts

問題

問題

提出解答

問題の概要

一週間が $N$ 日からなる世界を考える. 一週間は曜日 $1,2, \dots, N$ と進み, 曜日 $N$ の翌日は次の週の曜日 $1$ になる.

各曜日について, その曜日を平日とするか, 休日とするかを決定する. ただし, 少なくとも $1$ つの曜日については休日としなければならない.

平日と休日を決定した後, 曜日 $i$ の生産量を次のように決定する.

曜日 $i$ が休日ならば, 生産量は $0$ である.
曜日 $i$ が平日ならば, 曜日 $i$ の直前の休日が $x$ 日前, 直後の休日が $y$ 日後であるとき, 生産量は $A_{\min(x,y)}$ である.

各曜日の生産量の総和の最大値を求めよ.

制約

$1 \leq N \leq 10^9$
$1 \leq A_i \leq 10^9$

解法

対称性より, 曜日 $N$ を休日としてもよい.

また, ある休日のあと, 次の休日が $d$ 日後である場合を考える. このとき, $d$ 日間の間における生産量の総和は $d$ のみによって決定される.

$B_1, \dots, B_N$ を次のようにして定める.

$B_d$ を次の休日が $d$ 日後である場合, その間にある曜日における生産量の総和とする.

このとき,

$\displaystye B_d=\sum_{k=1}^{d-1} A_{\min(k, d-k)}$

である.

そして, 次のような動的計画法を考える.

${\rm DP}[d, t$ ] を次の休日が $d$ 日以内である場合を全て考慮した上で, $t$ 日間が経つときの生産量の最大値

ベースケースは $d=0$ のときで

${\rm DP}[0,t]=\begin{cases} 0 & (t=0) \\ -\infty & (t \neq 0) \end{cases}$

である. 更新式についても, $d$ 日を採用するかしないかで場合分けが発生し,

${\rm DP}[d,t]=\begin{cases} {\rm DP}[d, t-d] & (d \leq t) \\ {\rm DP}[d-1, t] & (d \gt t) \end{cases}$

である.

このとき, ${\rm DP}[N,N$ ] が解答になる.

計算量 $O(N^2)$ 時間で解くことができた.