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

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

グラフ問題

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

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

AtCoder ABC 282 D - Make Bipartite 2 (緑色, 400 点)

一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある! その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる!! 問題へのリンク 問題概要 頂点数 、辺数 の単…

AtCoder ABC 281 G - Farthest City (黄色, 600 点)

残り 1 分でなんとか通せた。 問題へのリンク 問題概要 頂点数 の連結な単純無向グラフ (頂点番号は であって、次の条件を満たすものの個数を で割ったあまりを求めよ。 なお、ここで、頂点 から各頂点 までの最短距離を としている。 制約 考えたこと グラ…

AtCoder ABC 280 G - Do Use Hexagon Grid 2 (赤色, 600 点)

ハニカムにそんな性質があるなんて!!! 45 度回転する技術のアナロジーが炸裂する。 あと、x 座標が最小となる点で場合分けする際に、同一の x 座標を持つものに対してダブルカウントを除去する工夫が大変だった。 問題へのリンク 問題概要 2 次元平面上に…

AOJ 2207 無矛盾な単位系 (UTPC 2010 D)

これも重み付き Union-Find で解ける問題! 問題へのリンク editorial 問題概要 具体例として一つの入力ケースを示す。 7 1 kilometre = 10^3 metre 1 megametre = 10^3 kilometre 1 metre = 10^-6 megametre 1 terametre = 10^3 gigametre 1 petametre = 10…

AtCoder ABC 087 D - People on a Line (ARC 090 D) (水色, 400 点)

重み付き Union-Find が有効活用できる問題! 問題へのリンク 問題概要 個の変数 の値を決定したい。 これらの値を決定するための 本の制約条件がある。このうち 個めの情報は 3 つの値 によって与えられ、 であるという制約条件を表す。 これら 本の制約条…

AtCoder ABC 280 F - Pay or Receive (青色, 500 点)

重み付き Union-Find が使える鮮やかな楽しい問題! 問題へのリンク 問題概要 頂点数 (頂点番号が ) のグラフが与えられる。このグラフには 組の辺があり、 組目の辺は、 頂点 から頂点 へと、長さ の有向辺 頂点 から頂点 へと、長さ の有向辺 となっている…

AtCoder ABC 246 G - Game on Tree 3 (黄色, 600 点)

めっちゃ面白い問題だった! 問題へのリンク 問題概要 頂点 0 を根とする頂点数 の根付き木が与えられます。頂点 0 以外の頂点 には数値 が書かれています。今、頂点 0 にコマが置いてあります。 高橋くんと青木くんが次の動作を交互に繰り返します。 青木く…

AtCoder ABC 245 E - Wrapping Chocolate (水色, 500 点)

これ!!! ABC 091 C - 2D Plane 2N Point とほとんど同じ!! ただ制約が大きいので、貪欲法を高速化する必要がありますね。 問題へのリンク 問題概要 個のチョコレートと、 個の箱があります。 番目のチョコレートはサイズ であり、 番目の箱はサイズ で…

AtCoder ABC 245 C - Choose Elements (茶色, 300 点)

EDPC C - Vacation と良く似た問題だと思う!! あと、幅が狭いグリッドでは DP が疑われることが結構多い! 問題へのリンク 問題概要 長さが の数列が 2 つ ( と ) 与えられます。 各 に対して、 と のいずれかを選ぶことで、新たに数列 を作ります。 こう…

AtCoder ABC 213 H - Stroll (赤色, 600 点)

オンライン分割統治 FFT 面白いね!! 公式解説がとても丁寧なので、備忘録程度に 問題へのリンク 問題概要 頂点数 のが与えられます。 組の頂点対に対して、次のように無向辺を張っていきます。 組めの頂点対に対しては 長さ 1 の辺が 本 長さ 2 の辺が 本 …

AOJ 2345 Network Reliability (JAG 冬コン 2011 F) (700 点)

ABC 213 G の類題に挙がっていたのでやってみた! 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。また 以上 以下の整数 が与えられます。 グラフの各辺は % の確率でそれぞれ独立に消失します。グラフ全体が連結である確率を求め…

AtCoder ABC 213 G - Connectivity 2 (橙色, 600 点)

面白かった!! より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…

AtCoder ABC 213 D - Takahashi Tour (茶色, 400 点)

DFS (深さ優先探索) の動きをシミュレーションする問題。 問題へのリンク 問題概要 頂点番号が であるような木が与えられます。 今このグラフにおいて、頂点 1 から出発して、次の動きを繰り返します。 いまいる頂点に隣接する頂点のうち、まだ訪れたことが…

yukicoder No.763 Noelちゃんと木遊び

いわゆる「木上の最大安定集合問題」です! 超典型問題です。 問題へのリンク 問題概要 頂点数 の木が与えられます。木からいくつかの頂点を選んで削除します。その結果、木はいくつかの連結成分に分かれます。 分かれた連結成分の個数の最大値を求めてくだ…

AOJ 1163 カードゲーム (ICPC 国内予選 2009 E) (400 点)

典型的な二部マッチングの問題です。 問題へのリンク 問題概要 枚の赤いカードと、 枚の青いカードとの間でマッチングを作っていきます。 各カードには整数値が書かれていて、最大公約数が 1 より大きいカード同士をペアにすることができます。 最大マッチン…

AOJ 2594 Reverse a Road II (JAG 模擬地区 2014 F) (600 点)

ネットワークフローアルゴリズムの構造をちゃんと理解しているかを問う良問ですね!! 問題へのリンク editorials 問題概要 頂点数 、辺数 の有向グラフ と、2 頂点 が与えられます。 いま、グラフの辺を 1 本選んで向きを反転させます。それによって、- 間…

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

「最短路に含まれる可能性のある辺を列挙する」という考え方と、最小カットを組み合わせます。教育的な良問といえますね。 問題へのリンク editorial なお、この問題の設定を少し変えると非常に難しい問題が得られることも知られています (難しい問題: AOJ 2…

AtCoder ABC 010 D - 浮気予防 (青色)

最小カットのよい練習問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられます。頂点番号を とします。また、頂点 0 以外の 個の頂点 が与えられます。 今、次の操作を行っていくことで、頂点 0 からは頂点 のいずれにも到達で…

AOJ 2536 Median Tree (JAG 模擬地区 2012 C) (400 点)

グラフの最小全域木の構造に関する理解を問う良問ですね。 問題へのリンク (AOJ) 問題へのリンク 2 (AtCoder) editorials 問題概要 連結な重み付き無向グラフ が与えられます (頂点数 、辺数 )。 の全域木のうち、全域木に含まれる 本の辺の重みのメディアン…

AtCoder ARC 005 C - 器物損壊!高橋君 (0-1 BFS) (水色)

通称 0-1 BFS と呼ばれるアルゴリズムが使える問題ですね。 問題へのリンク 問題概要 のマス目で表現された地図が与えられます。 . は通路、# は壁を表します。s マスから出発して、上下左右への移動を繰り返しながら g マスへと到達したいとします。. マス…

AtCoder ABC 049 D - 連結 (ARC 065 D) (青色, 400 点)

Union-Find を上手に使うと解けるいい練習問題ですね。 問題へのリンク 問題概要 個の都市があって、都市間を 本の「道路」と 本の「鉄道」が結んでいる。各道路と各鉄道は、結んでいる都市間を双方向に移動することができる。 各都市 に対して、以下の条件…

AtCoder ABC 075 C - Bridge (緑色, 300 点)

Union-Find や、DFS、BFS などで解ける問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフ が与えられます。 グラフ の辺 が橋であるとは、その辺を除去したときに、グラフが連結でなくなることを指すものとします。 グラフ におい…

AtCoder ABC 091 C - 2D Plane 2N Point (ARC 092 C) (水色, 400 点)

とても教育的かつ典型的な貪欲法の問題ですね。 問題へのリンク 問題概要 二次元平面上に、赤い点と青い点が 個ずつあります。 個目の赤い点の座標は であり、 個目の青い点の座標は です。 赤い点と青い点は、 座標と 座標がともに赤い点よりも青い点の方が…

AtCoder ABC 206 D - KAIBUNsyo (緑色, 400 点)

今や Union-Find やるだけだと茶色 diff (下手したら灰色 diff) だけど、ちゃんと考察要素を入れるとやっぱり緑色 diff になるのね。 問題へのリンク 問題概要 正の整数からなる整数列 が与えられる。以下の操作を好きなだけ行うことによって、 個の値がすべ…

AtCoder ABC 014 D - 閉路 (青色)

木上のパスに関する問題!! LCA で解決できる典型問題 問題へのリンク 問題概要 頂点数 の木が与えられる。次の 個のクエリに答えよ。 各クエリでは木上の 2 頂点 が与えられる 木に辺 を仮に追加したとすると、閉路が 1 個形成される その閉路に含まれる辺…

AtCoder ABC 019 D - 高橋くんと木の直径 (水色)

木の直径の求め方を知っていれば解ける!! 問題へのリンク 問題概要 頂点数 の木があるが、その形状についての情報はあらかじめわからない。あなたの目的は、この木の直径の長さを求めることである。 そのために、以下のクエリを 100 回まで投げることがで…

競プロ典型 90 問 003 - Longest Circular Road(★4)

木の直径を求めよ、という問題。直径を考えると解ける問題は高難易度でもお馴染みですね。 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 頂点数 の木が与えられます。 この木に新たに辺を 1 本追加すると、閉路が 1 つできます。 …

AtCoder ARC 115 C - ℕ Coloring (茶色, 500 点)

これ茶色はさすがにびっくりした! 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…

AtCoder ARC 115 D - Odd Degree (黄色, 600 点)

なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …