概要
公式解説がなさそうだったので書いておきます。→ 作問者解説が見つかったのでリンクしました。
愚直解法を数式にして、それを元に考察するのが最近の好みです。
$O(N^2)$ 解法
次のような dp を考えます。
- $\dp[i,j]$：$i$ 日間を終了した時点で、$j$ 回の自炊をしたとするとき、幸福度の総和の最大値。
次の解法は、すぐに出ると思います。
dp[0, 0] = 0
dp[0, 1:] = -INF
for i in range(N):
for j in range(N + 1):
dp[i + 1, j] = max(dp[i, j] + C[i], dp[i, j - 1] + P * (Q - i + 2 * j - 2))
ans = dp[N].max()これを変数変換して、より良さそうな解法を考えます。
漸化式の式変形
私の好みに合わせて、 $\dp[i,j]$ を $A_{i,j}$ と書いて、$C[i]$ を $a_i$ を書くことにします。漸化式 $$A_{i+1, j} = \max(A_{i,j} + a_i, A_{i, j-1} + P(Q – i + 2j – 2))$$ を観察します。
$B_{i,j} := A_{i,j} – Pj^2$ とおきます。すると、
$$\begin{align*}B_{i+1,j} &= A[i+1,j] – Pj^2 \\&= \max(A_{i,j} + a_i – Pj^2, A_{i,j-1} + P(Q – i + 2j – 2) – Pj^2)\\&=\max(B_{i,j} + Pj^2 + a_i – Pj^2, B_{i,j-1} + P(j-1)^2 + P(Q-i+2j-2) – Pj^2)\\&=\max(B_{i,j} + a_i, B_{i,j-1} + P(Q – i – 1))\end{align*}$$
となります。そこで改めて $b_i:= P(Q – i – 1)$ とすれば、$$B_{i+1,j} = \max(B_{i,j}+a_i, B_{i,j-1}+b_i)$$ となります。
片方の遷移を簡単に表すために、さらに変数変換します。
$$C_{i,j} := B_{i,j} – \sum_{k=0}^{i-1}a_k$$ とおきます。すると、
$$\begin{align*}C_{i+1,j} &= \max(B_{i,j} – \sum_{k=0}^{i}a_k + a_i, B_{i,j-1} – \sum_{k=0}^{i} a_k + b_i) \\ &= \max(C_{i,j}, C_{i, j-1} – a_i + b_i)\end{align*}$$
と変換されます。改めて $c_i := b_i – a_i$ とおけば、$$C_{i+1,j} = \max(C_{i,j}, C_{i,j-1} + c_i)$$ と変形できました。
$O(N\log N)$ 解法
あとは簡単です。$C_{0,0}$ から $C_{N,j}$ への遷移を考えると、$C_{N,j}$ は、$c_0, \ldots, c_{N-1}$ のうち大きい方から $j$ 個の和であることが分かります。
$B_{N,j} = C_{N,j} – \sum_{k=0}^{N-1} a_k$ により $B_{N,j}$ が求まり、$A_{N,j} = B_{N,j} + Pj^2$ により $A_{N,j}$ が全て計算できます。それらの $\max$ を答えればよいです。
コメント
最後まで変数変換でやりましたけど、$B_{i,j}$ の漸化式が得られた時点であとは簡単という感じがします。数列を変換して漸化式を簡単にしていくの、高校数学典型でしょうか。式変形に慣れていれば簡単にまねできると思います。
こういうのは、公式解説の類では（同じことでも）数式をいじるよりも、問題を上手く言い換える形で考察してあることが多い気がしますが、数式を向き合う方が個人的に簡単だということを最近発見しました。
