CODE FESTIVAL 2018 qual A D - 通勤

解法

後ろの方から見ていくと見通しが良くなるのかな、と思いきやそうでもありませんでした。
$dp[i] = i$ 番目のガソリンスタンドで燃料を補給する場合の、 $1$ ~ $i-1$ 番目のガソリンスタンドの建て替え方
とします。
仮に今燃料が満タンの状態で $p$ 番目のガソリンスタンドにいる場合、 $x\lt i$ となるi番目のガソリンスタンドで燃料を補給するには、
$F -T \lt X_i - X_p \leqq F$
を満たしている必要があります。
また、上の条件を満たすガソリンスタンドが複数存在した場合は、その一番手前のガソリンスタンドに到着した時点で、補給することになります。
逆に、 $F -T \geqq X_i - X_p$ を満たす区間のガソリンスタンドは、書店に変えても変えなくても結果が変わらないので、自由に決めることができます。
ということで、
$F -T \geqq X_i - X_p$ の区間内のガソリンスタンドの決め方が、 $F -T \lt X_i - X_p \leqq F$ の区間内で燃料を補給する場合のガソリンスタンドの建て替え方にかかわっていることがわかります。
これを式にすると、
$i$ 番目のガソリンスタンドから、正の方向で距離 $F -T$ 以内に存在するガソリンスタンドの個数を $n_i$ とし、
$i$ 番目のガソリンスタンドから、負の方向で距離が $F-T$ より大きく $F$ 以下の位置にあるガソリンスタンドの番号を $p_i$ とすると、
$dp[i] = dp[p_i]×2^{n_{p_i}}$
となります。
$p_i$ の候補が複数存在する場合はすべて足し合わせます。
$p_i$ の全候補は $O(N)$ で候補の左端、右端をそれぞれ調べることで求めることができます。
$n_i$ も、上と同様の操作を行うことで、 $O(N)$ で求めることができます。
あとは、
$dp[p_i]×2^{n_{p_i}}$ を、 $1$ ～ $p_i$ までの累積和として記録しておくことで、 $dp[i]$ について、O(1)で計算することができるようになるので、このdpが時間内に解けるようになります。
最後に、答えを求めるのですが、これは上と似たような操作を行うことで答えを求めることができます。
$i$ 番目のガソリンスタンドとDの距離が $F-T$ より大きく $F$ 以下であれば、上とまったく同じ操作を行えば答えが求まります。
$F-T$ 以下であれば、その距離内のガソリンスタンドの個数だけ、 $2^{(個数)}$ を $dp[i]$ にかけてあげてから足してあげることで、答えが求まります。
この計算により、最終的な答えが求まります。

ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

CODE FESTIVAL 2018 qual A D - 通勤

解法