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

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

密グラフ

AtCoder ABC 325 E - Our clients, please wait a moment (緑色, 450 点)

少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題! 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…

AtCoder ABC 210 F - Coprime Solitaire (橙色, 600 点)

2-SAT の「密」を解消する累積 OR テクを学んだ! 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。各カードについて、表を上にするか、裏を上にするかを選択していく。 上手く選択することで、上を向いている数値がどの 2 つも…

2-SAT で密な節を解消する方法

結論 先に結論から。 リテラル に対して、以下の条件 A, B, C は同値である。 A: のうち、True であるのは 1 個以下である B:任意の () に対して、節 を充足する C:新たなリテラル の値を適切に定めたとき、以下をすべて充足する 1:節 () 2:節 () 3:節…

AtCoder ABC 304 C - Virus (灰色, 300 点)

単純な DFS / BFS 系はいよいよ灰色 diff になったのですね。 問題へのリンク 問題概要 二次元平面上に 人がいます。 番目の人は座標 にいます。 今、 番目の人がウィルスに感染しました。ウイルスに感染した人から距離が 以内にいる人にウイルスは次々とう…

AtCoder ABC 282 E - Choose Two and Eat One (青色, 500 点)

これをグラフの問題だと思えるかどうか! 問題へのリンク 問題概要 箱の中に 個のボールが入っており、各ボールには 以上 以下の整数が書かれている。 番目のボールに書かれた整数は ​ である。 箱の中に 2 個以上のボールが残っている限り、下記の行動を繰…

JOI 春合宿 2007 day3-2 Route (難易度 7)

DIjkstra をするときに、直前の頂点ももつ系 問題へのリンク 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点 の座標は となっている。 頂点 1 から頂点 2 へと至る経路のうち、鋭角に曲がる箇所がないようなものを考える (頂点 の前の頂点…

AtCoder ABC 181 F - Silver Woods (黄色, 600 点)

条件反射で二分探索してしまった!!!この問題めっちゃ面白くて好き!!! 問題へのリンク editorial 問題概要 平面上に 2 直線 で囲まれた通路がある。この通路の中の の部分に 本の大きさの無視できる釘が打たれており、 本目の釘の座標は である。 高橋…

AOJ 2376 DisconnectedGame (JAG 冬合宿 2010 day3-H) (600 点)

こないだの ARC でめっちゃ似た問題が出たので!これは、SolveMe を含む、りんごさんによる伝説のセット。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 のグラフが与えられる (入力は の隣接行列で与えられ、初期状態では非連結である)。この…

Codeforces Grakn Forces 2020 G. Clusterization Counting (R2700)

めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…

AtCoder ABC 143 E - Travel by Car (青色, 500 点)

この Floyd--Warshall は天才すぎる! 問題へのリンク 問題概要 頂点 辺の重み付き無向単純グラフが与えられる。容量 の燃料タンクがあって、長さ の辺を通ると、タンクの燃料残量が だけ減少する。 各頂点では燃料を補給できて、補給すると満タン (容量 の…

AtCoder ARC 064 E - Cosmic Rays (青色, 600 点)

昔の AtCoder はこういうのもあったのか!!! 問題へのリンク 問題概要 二次元平面上に、 個の円がある。二次元平面上の点 から点 へと進むことを考える。秒速 1 だけ進む。 そのような方法のうち、円外の領域を進んでいる時間の最小値を求めよ。 制約 考え…

CS Academy 082 DIV1 E - Water Supply

ラグランジュ緩和か、、、 しかしこれ、ある特定の 1 頂点について次数が 以下であるような最小全域木を求める問題とみなせるわけだけど、こんなんが解けるのは面白い。 全域最小木スライドにある通り、全頂点について次数が 以下となるような最小全域木を求…

CS Academy 081 DIV2 E - Fold Polygon

の Kruskal 法ではダメで、 な Prim 法なら OK という稀有なパターンの問題。Dijkstra 法でも priority_queue を使ったやつは 愚直なやつは と二種類の実装があって前者の方が速いと言及されるケースも多いけど、密グラフ ( なグラフ) では後者の方が速い。P…