drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder 黄色diff ABC-F セグメント木 セグメント木上の二分探索 Dijkstra法 最短路問題 テーマにストーリー性のある面白い問題 グラフ 多点を扱う問題 グラフ上にチェックポイントのある問題 各kに対して DP値:ペア値 二分探索 伝播していく様子をテーマにした問題 AtCoder550点 NoviSteps3D セグ木上二分探索使ったというコメントをよく見たけど、僕の方針でも使うことになった 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き無向グラフが与えられる。 日目、 個の頂点 がウィルスに感染した。一度ウィルスに感染した頂点はずっと感染したままとなる。 ここで、 日目についてのウィルス感染条件を表すパラメータ が与えられる。 このとき、頂点 が 日目に初めてウィルスに感染する条件は、頂点 に隣接する頂点 が存在して、 日目までに頂点 はウィルスに感染している 辺 の重みが 以下である という条件を満たすことである。 各頂点 に対して、初めてウィルスに感染したのが何日目であるかを答えよ。… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F06%2F25%2F130110" title="AtCoder ABC 307 F - Virus 2 (3D, 黄色, 550 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2023-06-25 13:01:10 rich https://drken1215.hatenablog.com/entry/2023/06/25/130110 1.0 100%