けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

グラフの頂点を倍加する

AOJ 2956 ジャム (Jam) (HUPC 2019 day2-E)

こういうのを素早く解けるようになりたい 問題へのリンク editorial 問題概要 頂点 辺の重み付き無向グラフがある。各頂点 には そこで売ってるパンを買ったときの美味しさ そこで売ってるジャムの種類 そこで売ってるジャムを買ったときの美味しさ という 3…

AtCoder ABC 164 E - Two Currencies (青色, 500 点)

これ、頂点を倍加してダイクストラする系。 問題へのリンク 問題概要 頂点 辺の連結な無向グラフが与えられる。各辺 には 通行に要する料金 円 (所持金が 以上でなければ通行できない) 通行に要する所要時間 秒 という属性がある。また、各頂点 では所持金を…

Codeforces Round #616 (Div. 1) C. Prefix Enlightenment (R2400)

Union-Find を使いこなす!!! 問題へのリンク 問題概要 (意訳) 個の 0-1 変数 が与えられていて、最初はそれらの値について特に制約はない。いま、 個の制約が順に与えられる。各制約はそれぞれ 1 つの変数 と 0 か 1 の値 w を指定して、 とする 2 つの変…

AtCoder ABC 132 E - Hopscotch Addict (水色, 500 点)

こういうのを僕が初めて解いたのは、はまづさんのこの問題だった。 atcoder.jp そして、昔の ICPC などでは特に、この手の問題は何度も何度も出題されていた。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えらえる。頂点 から頂点 へと、けんけんぱで…