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

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

最適解に含まれる可能性がない要素を挙げる

Codeforces 552 DIV3 F. Shovels Shop (R2300)

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

AOJ 2171 Strange Couple (AOJ-ICPC 600 点)

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

AOJ 2872 最短距離を伸ばすえびちゃん (RUPC 2018 day3-F)

ABC 051 D - Candidates of No Shortest Paths をやった流れで。この問題なら自然だけど、ちょっと設定変えた問題に超グロ問があったりする (AOJ 2230 How to Create a Good Game)。 問題へのリンク 問題概要 頂点 辺の重み付き有向グラフが与えられる。グラ…

AtCoder ABC 051 D - Candidates of No Shortest Paths (400 点) 〜 3 通りの解法 〜

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