Codeforces Round #584 - Dasha Code Championship F. Koala and Notebook (R2600)

Codeforces 探索問題応用的な探索最適解に含まれる可能性がない要素を挙げる最短路問題 BFS グラフ問題 DFS DP 文字列を値にもつDP グラフの辺を分割する辞書順辞書順最小なグラフ探索数値を表す文字列同士の比較各kに対して数値のconcat

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

2019-04-18

Codeforces 552 DIV3 F. Shovels Shop (R2300)

Codeforces ソート Greedy DP 操作をK回まで行える探索順序を工夫して解く累積和前処理区間分割型シーケンシャルDP 数列二値パラメータ問題探索候補を絞る最適解の形を考える最適解に含まれる可能性がない要素を挙げる

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

2019-03-20

AOJ 2171 Strange Couple (AOJ-ICPC 600 点)

AOJ JAG AOJ-ICPC600点期待値ランダムウォーク期待値DP DP 連立一次方程式行列方程式最適解に含まれる可能性がない要素を挙げるグラフ問題最短路問題 Dijkstra法前処理自己ループを除く

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

2019-02-15

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

AOJ RUPC 自明な上界が最適解フローグラフ問題最短路問題グラフを変形する問題最小カット最適解に含まれる可能性がない要素を挙げるグラフの考えるべき辺数を減らす

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