ABC 401-500/ABC417D - Takahashi's Expectation - 競技プログラミング用 知識集積所【8/3更新】

---

問題

ABC417D

必要知識

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

• 動的計画法
• バックトレース
• 累積和
• 二分探索（未作成）

考え方

愚直にやってはTLEなので、高速化を考える。

プレゼント残り1つの状態で現在のテンションがわかれば、同じく最終的なテンションはすぐにわかる。
プレゼント残り2つの状態で現在のテンションがわかれば、1つもらった後のテンションを計算し、プレゼント残り1つのデータを見ればすぐにわかる。
プレゼント残り3つの状態で現在のテンションがわかれば、1つもらった後のテンションを計算し、プレゼント残り2つのデータを見ればすぐにわかる。
つまり、バックトレースで後ろから表を埋める動的計画法でいけそうだとわかる。

しかし、テンションの初期値が10^9であるため、そのままではDPテーブルの横幅が大きすぎてダメ。
そこで、AとBとPの上限が小さいことに着目する。
最初のテンションがそんなに高くなければ、実はテンションが1000を超えることは絶対にない。
そのため、テンション上限を1000としても、初期値が1000以下の場合については絶対に解ける。

では、初期値が1001以上の場合はどうするか？
これは、1000を切るまではテンションが下がり続けるしかないことを利用できる。
あらかじめBの累積和を出しておく。
そして、和が初めてx-1000より大きくになるところを二分探索（未作成）で探す。
見つけたところまでをまとめてテンションダウン扱いにすると、その時点で渡したプレゼントの個数とその時点でのテンション（1000未満）がわかるので、DPテーブルの途中部分を見て答えることができる。

最後までテンションダウンし続けてなお1000より高くなる場合、DPテーブルの範囲外を見る危険がある。
初期テンションがB全体の総和+1000以上の場合を分けてしまった方が無難。

解答例

解答例

注意点

別解