drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ DP DP高速化 DP高速化:累積和 累積和 数え上げ問題 区間分割型シーケンシャルDP シーケンシャルDP 体力や燃料がある一定以上必要になる設定の問題 unrated公式コン AtCoder AtCoder700点 数直線上のN点の問題 二分探索:lower_bound 点が移動していく問題 解空間:O(2^N)通りの選択肢 区間分割の仕方を走査する問題 DP状態:前回の最後の場所 ひたすらバグってつらかった。。。DP 高速化系。セグ木を使ってもいいが、累積和だけで解ける。 問題へのリンク 問題概要 座標 地点から座標 地点へと移動する。 移動途中に 個のガソリンスタンドがあって、それらの座標は で与えられる。 燃料 の状態でスタートして から まで途中で一切止まることなく移動する 1 移動するごとに燃料を 1 失う ガソリンスタンド地点を通過するときに燃料が 未満だったら一瞬で になる ガソリンスタンドまたは地点 以外の場所で燃料が になったらダメ さて、ガソリンスタンドを何個か壊すことを考える。壊して良いガソリンスタンドの集合の個数を 1000000007 で割ったあ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2018%2F09%2F23%2F141400" title="CODE FESTIVAL 2018 qual A D - 通勤 (700 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2018-09-23 14:14:00 rich https://drken1215.hatenablog.com/entry/2018/09/23/141400 1.0 100%