最短経路
内容 公式解説と違う解き方なのでメモ。 問題 リストAとクエリ(L,R,X)が与えられる。 Aの区間[L,R]に含まれる 数字X の個数を求める。 atcoder.jp 考えたこと(1-originで書いてます) F(L,R) =Aの区間[L,R]に含まれる 数字X の個数とする。 F(L,R) = F(1,R)-F…
内容 CodeForces 712 Div2 E問題を、pythonでといた 問題 codeforces.com 考えたこと TSPだけど、N<=10*5なので、greedyとかで行けそう。 beautyが大きいところから、小さいところには、cでいける。 一番beautyが大きい都市まで行けば、あとは、残りを辿るだ…
内容 ABC137 E問題Coins Respawnをpythonで解きました。 問題 atcoder.jp 考えたこと 問題見た感じ、辺のコストを(-cost+P)にして、負の辺がある最短経路問題じゃんと思った。 負の重みの辺があるので、ダイクストラは使えなくて、 ベルマンフォード を使う…