「最短路に含まれる可能性のある辺を列挙する」という考え方と、最小カットを組み合わせます。教育的な良問といえますね。 問題へのリンク editorial なお、この問題の設定を少し変えると非常に難しい問題が得られることも知られています (難しい問題: AOJ 2…

グラフの最小全域木の構造に関する理解を問う良問ですね。 問題へのリンク (AOJ) 問題へのリンク 2 (AtCoder) editorials 問題概要 連結な重み付き無向グラフ が与えられます (頂点数 、辺数 )。 の全域木のうち、全域木に含まれる 本の辺の重みのメディアン…

とても面白い問題です！ 問題へのリンク 問題概要 頂点数 、辺数 の、連結な重み付き無向単純グラフ が与えられる。 このグラフの「最小全域木」はさまざまなものが考えられるが、そのすべてに含まれるような辺の集合を考える。 その集合の要素数と、その集…

素直に考えるとグラフの辺数が のオーダーになってしまうので、いかに削減するかを考える問題だった 問題へのリンク editorials 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。各頂点 には値 が振られている。今、各頂点にスコア を割り振りたい。…

これは天才！！！ 問題へのリンク 問題概要 一直線上に 個の点が順に並んでいる (座標が )。 個のクエリが与えられる。 各クエリでは区間 () が与えられる 個の点のうち のみを取り出してできる 個の点について以下の問に答えよ 与えられた点集合から、どの …

BFS 木とか、BFS による経路復元とか、その辺りの理解を問いかける教育的問題だった！！！ 問題へのリンク 問題概要 頂点、 辺の無向グラフが与えられる。頂点 1 以外のすべての頂点に対し「みちしるべとなる頂点」を、以下の条件を満たすように設定すること…

似たようなことは考えたことがあった。経路復元に関する理解を問う教育的問題！ 問題へのリンク 問題概要 重みなしの有向グラフと、2 頂点 s, t を始点と終点にもつパスが与えられる。今、われわれはナビに沿ってこのパスをたどっている。ナビの仕様は次の通…

勉強になった！！！！！ 「辺番号または頂点番号が辞書順最小な最短路」を求める考え方が炸裂する感じ。 最短路として使われうる辺を列挙しておく (この考え方自体が典型) その辺をうまいこと活用しながら探索する という典型の流れになっている。 問題への…

問題概要 個の品物があって、それぞれ価格は である。ここから 個の品物を何回かに買いたい。ここで一回の買い物につき一回ずつ使えるクーポン券が 個あって (使わなくても良い)、各クーポンは ちょうど 個の品物を買ったならば、そのうちの安い順に 個の品…

ランダムウォークな問題！ 実数係数の連立方程式の練習に 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。ただし自己ループを含み得る (多重辺はない)。二頂点 が指定されていて、 から へとランダムウォークによって辿り着きたい。 ただし…

「最短路として選ばれる可能性がないところを挙げる」というのは、それ自体、高難易度問題で部分的に必要になる考察だったりするね。 問題へのリンク より高難易度な問題の部分問題となる例として、 RUPC 2018 day3-F 最短距離を伸ばすえびちゃん がある。こ…