ダメージの最大値 \(D\) を目標値として決め打った場合の判定問題を解くことを考えます。

便宜上

• \(A_0 = T\) としておきます。
• \(A_N\) を得たあと、コインを渡してカード交換をするとします（\(K\) に \(1\) を加えておきます）。

判定問題の最短路問題への言い換え

カード \(v_0=0, \ldots, v_n\)（\(v_0 = 0, v_n = N\)）をカード交換対象とするとき、ダメージ最大値が \(D\) 以下になるかどうかを考えます。これは、任意の区間 \([v_i, v_{i+1}]\) に対する条件（\(j\in [v_i, v_{i+1}]\implies |A_j-A_{v_i}|\leq D\)）として書けます。

したがって区間 \([v, w]\) が valid であるような \(v, w\) 間に重み \(1\) の有向辺を張ったとき、\(0\) から \(N\) までの最短距離が \(K\) 以下であるかを判定すれば、判定問題を解くことができます。

グラフの構築

上のような \((v,w)\) 全てに辺を張っていては辺が多すぎます。遷移できる \((v,w)\) 全体は区間であることを利用して、次のようなグラフで置き換えます。 - \(v\) に対して、区間 \([v,w]\) が valid であるような \(w\) のうち最大のものを求める。 - \(v\) から \(w\) へ重み \(1\) の有向辺を張る。 - 各 \(v\) に対して、\(v\) から \(v-1\) への重み \(0\) の有向辺を張る。

これで、頂点数・辺数が \(O(N)\) のグラフになります。辺の重みは \(0, 1\) のどちらかなので、最短路問題は 01-bfs により \(O(N)\) 時間で解くことができます。

「\(v\) に対して、区間 \([v,w]\) が valid であるような \(w\) のうち最大のものを求める」部分については、例えば sparse table を用いて二分探索すれば、\(O(\log N)\) 時間で求めることができます。したがって、グラフの構築は \(O(N\log N)\) 時間で行えます。

答を二分探索することと合わせて、全体として \(O(N\log N\log A_{\max})\) 時間で答を求めることができます。