第１６回日本情報オリンピック本選 B - 準急電車 (Semiexpress)

お題箱より。

解法

後戻りできないこと、急行が停まる駅には必ず準急も停まることから、駅 $1$ からある目的駅までの最適な移動経路は「行けるところまで急行で行く→行けるところまで準急で行く→残りは普通で行く」となります。

そのため準急駅を足した時に所要時間が短縮される駅は、その準急駅以降で、かつ次の準急駅・急行駅より手前にある駅に限定されます。急行駅をまたがる形で影響を与え合うことはないため、急行駅ごとに区切ったエリアで分けて考えてみましょう。

以下の図のように急行駅ごとに区切ったエリアの1つを考え、その中で「何もしなくても時刻 $T$ 以内に到達できる駅」がどこまでかを調べます。もしこのエリア内に1つだけ準急駅を置けるとすると、以下の図のように到達可能範囲のすぐ右側に置くことが最適になります。

f:id:betrue12:20200306233652p:plain

このエリアにもう1つ準急駅を置いて良いとしましょう。このときも、先ほど置いた準急駅によって到達可能になった範囲のすぐ右側に置くことが最適です。

f:id:betrue12:20200306234213p:plain

その理由は以下の通りです。このエリアのどこかに準急駅を1つ置いて到達可能にすることができる駅の数は、既に到達可能な駅と被っていない場合、その駅が右側にあるほど少なくなります。具体的は、駅 $1$ からその準急駅までの到達時間を $t$ とすると、到達可能にすることができる駅数は

$T \lt t$ のとき $0$
$T \ge t$ のとき $1 + \lfloor\frac{T - t}{A}\rfloor$

で計算されます。エリア内では準急駅を右側に置くほど $t$ の値が大きくなるので、到達可能にできる駅数は少なくなることが分かります。

そして複数の準急駅によって到達可能にすることができる駅の範囲を被らせることには得は無いので、「前から詰めて置く」ことが最適になります。

こう考えると、このエリア内においてまず「何もしなくても到達可能な駅はいくつ（どこまで）か？」を求め、それから「1個目の準急駅を置いた時に新しく到達可能になる駅はいくつか？」「さらに2個目の準急駅を置いた時に…」という風に、準急駅を1個置いた時に新しく到達可能になる駅数を $0$ になるまで順次求めていくことができます。この数列は先ほど書いた理由から単調減少になり、このエリア内に $k$ 個準急駅を置いた時に増やせる到達可能駅数の最大値は常に「この数列の前から $k$ 個の和」になります。

実際には鉄道全体は $M$ 個のエリアに分かれていて、そこに合計で $K-M$ 個の準急駅を新しく置くことができます。この時も、以下のように考えることができます。

急行駅で区切られた全てのエリアに対して、まず「何もしなくても到達できる駅数」を答えに加算し、先ほどの「準急駅を1個置いたときに新しく到達可能になる駅数」たちを求める。
上記で得られた「準急駅を1個置いたときに新しく到達可能になる駅数」たちを全エリアについてひっくるめて降順ソートした数列を $X$ とする。 $X$ の大きい方から $K-M$ 個取って答えに加算する。

これでOKです。各エリアにどのように準急駅を割り振ったとしても、各エリアごとの最適値は結局 $X$ に含まれている要素の和になるので、 $X$ 全体で大きい方から取っていくのが全体最適になります。

駅数が多いので、各エリアごとに置く準急駅の数は $K-M$ 個までで打ち切りましょう。こうすれば $X$ の要素数は高々 $M(K-M)$ 個になりソート込みでも間に合います。もしくは公式解説にも書かれているように、優先度付きキューなどを使って $M$ 個のエリアを並列で進めながら一番利得が大きいところを取り続けていく、ということもできます。