ABC 401-500/ABC408F - Athletic - 競技プログラミング用 知識集積所

---

問題

ABC408F

必要知識

B以下レベルの内容は省略

• 逆写像（未作成）
• 動的計画法（未作成）
• segment木（未作成）

考え方

上から下へしか移動できないので、高い足場から順に動的計画法（未作成）でその足場への最大ステップ数を決めていけばよい。
ということは、データは「どの位置の足場がどの高さ」ではなく「どの高さの足場がどの位置」の方が使いやすいので、逆写像（未作成）で受け取る。

行動可能範囲でのステップ数の最大値は、途中で値を次々と書き換えるのでsegment木（未作成）を使う。
ただし、ステップ数が決まってすぐ反映すると、足場の高さの差がdないところも含めた最大値しかとれなくなってしまう。
そこで、ステップ数が決まったらqueueに入れておき、d回後のループで遅れて反映することでその問題を回避する。
最後の足場まで処理が終わっても、queueの中身を吐き出すのを忘れないように。

解答例

解答例

注意点

別解