燃料補給系問題
JOI
JOI本選
JOI難易度8
DP
DP値を利用して状態復元
Dijkstra法
最短路問題
燃料補給系問題
グラフ問題
AtCoder
AOJ
最適解の形を考える
解を変形していく(最適性を失わずに)
固定する変数を入れ替えて考える
ある量を固定して考える
今が良いほど未来も良いGreedy
Greedy
ある量を決めるとGreedy
dp の値そのものを用いて現在状態を復元する系の問題。 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 個の木 があって、それぞれ高さは である。 フクロモモンガは最初は、木 1 の高さ の地点にいる。フクロモモンガは木を飛び移り…
Codeforces
二値パラメータ問題
セグメント木
StarrySkyTree
差分更新
ある量を固定して考える
二分探索
ソート
探索順序を工夫して解く
lower_bound
累積max
CodeforcesDIV1-C
CodeforcesR2000
燃料補給系問題
価格に関する問題
遅延評価
セグ木を使って差分更新していく系、解けるけど実装が苦手すぎるので、こういうのをスパッと書けるようになりたい! 問題へのリンク 問題概要 個の武器と、 個の盾を持って、 体の敵に立ち向かう。あたなは武器の中から 1 個、盾の中から 1 個を選ぶ (初期状…
AtCoder
AtCoder500点
Greedy
固定する変数を入れ替えて考える
Dijkstra法
DP値:二値
DP
Floyd-Warshall法
最短路問題
燃料補給系問題
グラフ問題
密グラフ
今が良いほど未来も良いGreedy
前処理
クエリ処理問題
青色diff
この Floyd--Warshall は天才すぎる! 問題へのリンク 問題概要 頂点 辺の重み付き無向単純グラフが与えられる。容量 の燃料タンクがあって、長さ の辺を通ると、タンクの燃料残量が だけ減少する。 各頂点では燃料を補給できて、補給すると満タン (容量 の…
DP
DP高速化
DP高速化:累積和
累積和
数え上げ問題
区間分割型ナップサックDP
ナップサックDP
燃料補給系問題
unrated公式コン
AtCoder
AtCoder700点
一直線上のN点の問題
lower_bound
点が移動していく問題
ひたすらバグってつらかった。。。DP 高速化系。セグ木を使ってもいいが、累積和だけで解ける。 問題へのリンク 問題概要 座標 地点から座標 地点へと移動する。 移動途中に 個のガソリンスタンドがあって、それらの座標は で与えられる。 燃料 の状態でスタ…