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

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

グラフ上にチェックポイントのある問題

AtCoder ABC 307 F - Virus 2 (黄色, 550 点)

セグ木上二分探索使ったというコメントをよく見たけど、僕の方針でも使うことになった 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き無向グラフが与えられる。 日目、 個の頂点 がウィルスに感染した。一度ウィルスに感染した頂点はずっと感染し…

AtCoder ABC 304 E - Good Graph (緑色, 475 点)

Union-Find 慣れしていれば解きやすい! 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフ が与えられる。 組の頂点対 について、どの頂点対間のもパスがないグラフを良いグラフと呼ぶことにする。 与えられるグラフ は良いグラフである。 このグラ…

AOJ 2567 SIRO Challenge (JAG 模擬地区 2013 C) (400 点)

「ABC 301 E - Pac-Takahashi」の類題とも言うべき ICPC 系の問題! 問題へのリンク (AOJ) 問題へのリンク (AtCoder) editorials 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点番号は とする。 番目の辺は頂点 を結んでおり、その重みは …

AtCoder ABC 301 E - Pac-Takahashi (青色, 475 点)

前処理して頂点数を減らしたグラフ上で TSP!!! ICPC ではすごくよく見るパターンですね! 問題へのリンク 問題概要 サイズのグリッドがある。各マスは 壁マス:'#' 通路マス:'.' お菓子マス:'o' (18 個以内であることが保証される) スタートマス:'S' …

AtCoder ABC 073 D - joisino's travel (水色, 400 点)

Floyd-Warshall で前処理してどうのこうのする問題。特に ICPC 系などでよくある! 問題へのリンク 問題概要 頂点 辺の重み付き無向グラフが与えられる。 このグラフ上で 個のチェックポイントをなす頂点集合が指定されている。好きなチェックポイントからス…

AOJ 2200 Mr. リトー郵便局 (ICPC 模擬国内 2010 D) (500 点)

問題文長い... 問題へのリンク 問題概要 頂点、 辺の重み付き無向グラフが与えられる。各辺は「陸路」「海路」の属性がある。このグラフを、最初頂点 にいて、 の順番に最短時間で巡りたい (順番的に後の頂点を先に通ってもよいが、その頂点より前の指定頂点…