H - Candles 解説 by Nachia

別の角度からの考察

公式解説とは別の角度から考察します。

明らかにそれぞれのろうそくの火はすでに燃え尽きていない限り訪れた瞬間に消すのが最善です。また、\(10^{100}\) 分は十分に長いため、すべてのろうそくのある座標を訪れるとして良いです。(燃え尽きた後に訪れるものも含みます。)そして、訪れるろうそくの順番を \(1\) つ定めると、最短距離、最速で次のろうそくへ向かうのが最適です。これより、常に速度は \(1\) 、また方向転換はろうそくのある地点でしか行わないとして良いです。(公式解説の冒頭部分)

ろうそくは座標の昇順にソートしておきます。( \(A_1 \leq A_2 \leq \cdots \leq A_N\)

\(2\) つのテーブル \(\mathrm{dpL}[l][r],\mathrm{dpR}[l][r]\) \((1\leq l \leq r \leq N)\) を使って動的計画法を行います。

\(\mathrm{dpL}[l][r]\) は関数で、 \(\mathrm{dpL}[l][r](x)\) \((xは実数)\) の値を以下で定義します。

\(l \lt i \leq r\) について \(i\) 番目のろうそくは無視し、その他はまだ火を消されていない。今は時刻 \(0\) から \(x\) 分後で、高橋君は座標 \(A_l\) にいる。 この後高橋君が最適に行動したときのろうそくの長さの総和の最大値を \(\mathrm{dpL}[l][r](x)\) とする。

\(\mathrm{dpR}[l][r]\) について、 \(l\) 番目のろうそくの代わりに \(r\) 番目のろうそくが残っていて、高橋君が座標 \(A_r\) にいる以外は \(\mathrm{dpL}[l][r]\) と同様です。

すると、計算量はともかく、 \(\mathrm{dpL}[l][r],\mathrm{dpR}[l][r]\)\(r-l\) の大きい順に求めることができます。

この関数 \(\mathrm{dpL}[l][r](x),\mathrm{dpR}[l][r](x)\) は、実は傾きが \(0,-1,-2,-3,\cdots ,-N\)\(y\)切片が整数の一次関数いくつかの最大値で表せます。以下は、動的計画法で必要な変形です。

  • 高橋君が距離 \(d\) 移動する

    傾き \(a\) の直線の切片が \(ad\) 減少します。

    この変形は、 \(\mathrm{dpL},\mathrm{dpR}\) 間の遷移や、区間を縮める際に必要です。

  • \(k\) 番目のろうそくの火を時刻 \(0\)\(x\) 分後に消す

    \(y=\max\{0,X_k-x\}\) を足します。点 \(X_k\) での値が最大である直線を \(1\) つ選び、その直線より傾きが小さい直線の傾きを \(1\) 減少、 \(y\)切片を \(X_k\) 増加させることになります。傾きが増加する回数はろうそくの数なので、 \(N\) 以下です。

  • \(2\) つの関数の大きいほうをとる

    各傾きで、切片の大きいほうをとればよいです。

  • 始めに、座標 \(0\) から移動する

    \(\mathrm{dpL}[k][k]\) の状態から高橋君が距離 \(|A_k|\) だけ移動することにすればよいです。

以上より、計算量 \(O(N^3)\) で答えが求まります。

解答例 (C++,321ms)

投稿日時:
最終更新: