少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題！ 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…

とてもややこしくてハマってしまった......。とても教育的な Greedy 問題。 問題へのリンク 問題概要 個の商品がベルトコンベアで運ばれてくる。 番目の商品は、時刻 から時刻 の間 (両端含む) に点字できる。 点字マシンは 1 秒あたり 1 個の商品にしか点字…

よくある区間分割の DP だけど、それでよいことに思い至るのが難しいかもしれない。 問題へのリンク 問題概要 曲あって、それぞれの曲の長さは である。 今、時刻 0 から開始して「曲を一様ランダムに流し、それが終わったらまた一様ランダムに曲を選択して…

この問題をキッカケに準完全二分木のライブラリを拡充した！ 問題へのリンク 問題概要 頂点数 の根付き木が与えられる。頂点番号は である。各頂点 (> 2) について、親頂点は である。 この根付き木において、頂点 からの距離が であるような頂点の個数を求…

色んな解法がありそう。今回は、あまり解説書かずに備忘録程度に。 問題へのリンク 問題概要 長さ の数列 がある。各要素は 以上 以下の整数値である。 制約 メモ 各値ごとに考えていった。つまり、 として、 について求めていった。 各 について、 となる添…