この解説は本質的には公式解説と同じものです。公式解説との差分は解法にいたるまでの気持ちの説明と、DPテーブルを埋める向きです。

ろうそくを座標順にソートしなおして番号を振り直しておきます。また、座標 \(0\) に長さ \(0\) のろうそくがあるとして良いです。これを \(z\) 番目のろうそくとしておきます。

問題を次のように読み替えます。

「ろうそくは燃え続けると長さが負になることもありえます。高橋君は、自分と同じ位置にあるろうそくの火を消して回収または破棄することができます。回収したろうそくの長さの和がスコアとなります。スコアの最大値を求めてください」

以下ではろうそくが回収または破棄され、数直線上から取り除かれることを「処理される」と表現します。

公式解説と同様の考察により、高橋君は常に最速で移動し、(最終的に回収しないろうそくは目の前を通過する時に破棄するとして良いため)処理済みのろうそくは区間をなすことがわかります。したがって次のような区間DPを考えることができます。

\(DP[L][R][f][T]=\) \(L\) 番目から \(R\) 番目までのろうそくを処理し、時刻 \(T\) に区間の( \(f\) ? 左端 : 右端)にいるときのスコアの最大値

当たり前ですが、\(T\) は非常に大きな値を取りうるため、このままではACすることができません。スコアも大きな値になりうるため、keyとvalueの入れ替えにより状態数を削減することもできません。ろうそくの長さは時刻とともに変化するため、なんらかの形で時刻に関する情報を持つ必要があるように思えます。

ここで、時刻による影響は「このあと回収するろうそくの本数」のみに依存することに注意します。すなわち、たとえばこのあとろうそくを \(5\) 本回収するつもりがあるときに \(1\) 分無駄にすることは、最終的なスコアを \(5\) 無駄にすることに等しいです。このことに気づくと、最終的に回収するろうそくの本数を決め打つことで、時間の経過によりろうそくが短くなる影響を先取りすることができます。すなわち、問題を次のように読み替えることができます。

「ろうそくの長さが時刻により変化することはありません。ただし、このあと \(C\) 本のろうそくを回収する予定がある場合、\(1\) 分経過するごとにスコアが \(C\) 減少します(スコアは負にもなりうる)」

今までの考察を総合すると、この問題は明らかに次のようなDPを用いて解くことができます。

\(DP[L][R][f][C]=\) \(L\) 番目から \(R\) 番目までのろうそくを処理し、区間の( \(f\) ? 左端 : 右端)にいて、このあとさらに \(C\) 本のろうそくを回収する予定があるときのスコアの最大値

これは状態数 \(O(N^3)\) であり、\(DP[L][R][f][C]\) からの遷移先は \(DP[L-1][R][True][C]\), \(DP[L-1][R][True][C-1]\), \(DP[L][R+1][False][C]\), \(DP[L][R+1][False][C-1]\) の高々 \(4\) つであるため全体で \(O(N^3)\) で計算できます。

初期状態は \(i=0,1,\ldots,N\) に対して \(DP[z][z][True][i]=0\)、それ以外は \(-\infty\) であり、最終的な答えは \(\displaystyle \max_{l,r,f} DP[l][r][f][0]\)となります。

なお、適切な実装により空間計算量を \(O(N^2)\) にすることもできます。