https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_d
点0から数直線上を進み、座標$D$を目指す。$N$個のガソリンスタンドがあり、$i$番目のガソリンスタンドは座標$X_i$にある。車には最初$F$リットルの燃料が入っていて、1進むたびに1リットルの燃料を消費する。ガソリンスタンドに到着したとき、燃料が$T$未満であれば補給する。ここで、ガソリンスタンドをいくつか潰したい。点0から出発して座標$D$にたどり着けるようなガソリンスタンドの潰し方の総数を求めよ。
DPテーブルを $$DP[i]=i{\rm 番目のガソリンスタンドで補給する場合のi番目までのガソリンスタンドの存在のしかたの数}$$ とする。このDPは前から配るDPで更新できて、遷移は以下のようである。
$i$番目のガソリンスタンドで補給したあと、次にどこで補給することになるかを考える。ガソリンが$T$以上残っている場合はガソリンスタンドを通っても補給しないので、$X_i$超過$X_i+(F-T)$以下の座標にあるスタンドではどうやっても補給できないことになる。よって、この範囲のガソリンスタンドはどのように潰してしまっても問題なくて、この範囲に$k$個のスタンドがあれば$2^k$通りの潰し方が存在する。
$X_i+(F-T)$超過$X_i+F$以下の座標に存在するスタンドは、次に補給するスタンドの候補である。この範囲に$l$個のスタンドが存在するとき、(この範囲のなかで)はじめのスタンドを潰さなければ次に補給するのはそのスタンドになる。それを潰すのであれば、2番目のスタンドで補給することになる。このように、この範囲に属するスタンドで次に補給するためにはその前のスタンドをすべて潰すことが必要であり、そこに自由度は存在しない(そのスタンドまでについて、それぞれ1通りである)。
$X_i+F$より遠くに存在するスタンドで次に補給することはないので、これは考えなくてもよくて、以上のことから、DPの遷移は、$X_i+(F-T)$超過$X_i+F$以下の座標に存在するスタンドすべてに対して$DP[i]*2^k$をかけることであるとわかる。より簡潔に記述するためには、スタート地点である座標0に最初のスタンドが存在することにしたり、座標Dにもスタンドが存在することにして、ここでは燃料の残量に関わらず必ず補給することにしたりと工夫が必要である。このようにすれば、最終的な答えはDP[座標Dのindex]となる。区間加算の方法についてはBITを使えば可能である(tech006参照)。
本番中は予選に通過することが第一目標であったので、Cを解いても予選を通過できる見込みがないと判断した段階でDに切り替えた（結局解けなかった）。DPはあまり得意でないので練習を重ねたい。