グラフや盤面が時間変化する最短路問題
AtCoder
AtCoder450点
ABC-E
緑色diff
密グラフ
Dijkstra法
グラフ
最短路問題
【問題集】最短路問題
グラフや盤面が時間変化する最短路問題
DP状態:フェーズ(耳DP)
グラフの頂点を倍加する
典型要素を詰め合わせた教育的問題
最小コスト
所要時間を求める問題
最適化問題
少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題! 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…
AtCoder
AtCoder500点
unrated公式コン
迷路
二次元グリッド
グラフや盤面が時間変化する最短路問題
最短路問題
テク:循環するものを二週させる
操作列が文字列で与えられる
Greedy
最適化テク:解を変形していく(最適性を失わずに)
典型要素を詰め合わせた教育的問題
単調性に着目する
Greedy:今が良いほど未来も良い
壁マス
各地点に早くたどり着いておくに越したこと無い系問題!! atcoder.jp 問題概要 のグリッドがあってスタートからゴールへと行きたい。壁のあるマスは通れない。 ただし毎秒ごとに移動できる方向に制限がある。 で割ったあまりがそれぞれの場合についてどの方…
整数の三分探索は闇... 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。時刻 0 に頂点 を出発し、頂点 まで移動するのに要する最小時間を求めよ。 各辺にはパラメータ が設定されていて、時刻 にその辺の片側の頂点から出発した場合、もう片側の…