2022-12-07から1日間の記事一覧
AtCoder
AtCoder500点
ABC-E
青色diff
Union-Find
重み付きUnion-Find
データ構造
グラフ
負閉路
グラフのconnectivity
最短路問題
牛ゲー
双対性
クエリ処理問題
クエリ(グラフ上)
前処理
解空間:O(N^2)通りの選択肢
最長路問題
NP困難(特殊構造なので解ける)
重み付き Union-Find が使える鮮やかな楽しい問題! 問題へのリンク 問題概要 頂点数 (頂点番号が ) のグラフが与えられる。このグラフには 組の辺があり、 組目の辺は、 頂点 から頂点 へと、長さ の有向辺 頂点 から頂点 へと、長さ の有向辺 となっている…
AtCoder
AtCoder500点
ABC-E
水色diff
DP
回数の期待値
期待値
期待値DP
期待値の線形性
二項係数
特定の場所を決め打つことで単純な場合に帰着する
敵やモンスターのHPを削って倒していく問題
そのまま覚えたい典型問題
有理数mod998244353
EDPC A - Frog 1 とほとんど同じ DP で解けますね! 問題へのリンク 問題概要 体力が であるモンスターが 1 体います。高橋君はモンスターに対し、モンスターの体力が 1 以上残っている限り繰り返し攻撃を行います。 高橋君は 1 回の攻撃で、 の確率でモンス…