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

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

DFS

AtCoder ARC 065 D - 連結 / Connectivity (400 点)

Union-Find 木に関するすごくいい感じの問題 問題へのリンク 問題概要 個の駅がある。 本の道路と 本の鉄道があって、それぞれ双方向に駅ペアを結んでいる。 各駅に対して、その駅から道路のみを使っていくことができて、かつ鉄道のみを使ってもいくことがで…

AtCoder ARC 065 E - へんなコンパス / Manhattan Compass (900 点)

めるアイコン変換すると良さそうなのはすぐに思い至った。そこから繋げられずに editorial を見た。 問題へのリンク 問題概要 二次元平面上に 個の点がある。このうちの 2 点 が指定されている。その 2 点間のマンハッタン距離を とする。 この 点について「…

Codeforces 500 DIV1 B. Chemical table (R1900)

確かに、ついこの間の ABC 131 F の類題だね 問題へのリンク 問題概要 のグリッドがあって、 マス分が黒く塗られている 長方形の三頂点状に並んだ黒マスの組を選んで、残りの頂点に相当する位置を黒く塗る (コスト 0) 黒くないマスを一つ選んで黒く塗る (コ…

AtCoder AGC 014 D - Black and White Tree (900 点)

最高に好きな問題 問題へのリンク 問題概要 頂点数 のツリー上でゲームを行う。高橋君は残った頂点から 1 つ選んで白く塗る。青木君は残った頂点から 1 つ選んで黒く塗る。 この操作をすべての頂点に色が塗られるまで繰り返したとき、黒く塗られたすべての頂…

AtCoder ABC 126 D - Even Relation (400 点)

とても教育的なツリーの探索問題。 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。このグラフの各頂点を白黒に塗る方法であって 同色に塗られた 2 頂点はどれを選んでも、その間のパスの長さは偶数である という条件を満たすものを求めよ…

AtCoder ABC 114 D - 756 (400 点)

editorial は「75」という整数の特徴をフル活用している。 そして 75 という整数の特徴を活用しない DP による方法もあると説いている。 ここでは 75 という整数の特徴も活用せず、DP もしない (といっても DP への改良は容易) 愚直な全探索でも通った。 問…

diverta 2019 F - Edge Ordering (1200 点)

こういうの素早く解けるようになりたいね。 いわゆる「トポロジカルソート順の数え上げ」という高難易度でたまに見るパターンの問題。 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。ここで、辺 が全域木を形成していることが保証されている。 …

Codeforces 554 DIV2 E. Neko and Flashback (R2500)

面白かった 問題へのリンク 問題概要 (やや意訳) 長さ の数列 を復元したい。この数列に対し、ある並び替え順列 があって 隣り合う 2 要素の min をとってできる長さ の数列を で並び替えると となり 隣り合う 2 要素の max をとってできる長さ の数列を で…

AtCoder AGC 032 C - Three Circuits (800 点)

見るからにコーナーケースが怖い... atcoder.jp 問題概要 頂点 本の辺からなる単純かつ連結な無向グラフが与えられます。 全ての辺をちょうど一回ずつ使って つのサーキットを作ることが可能かどうかを判定してください。 制約 考えたこと 輪っかを 3 つ作る…

AOJ 1131 Unit Fraction Partition (ICPC 国内予選 2004 C)

有理数ライブラリ整備とか大げさなことせずに全探索頑張るのが本筋であろうが、ここでは有理数ライブラリの足し算の verify としてやってみた。 問題へのリンク 問題概要 有理数 p/q を n 個以下の 1/r な形の有理数の和として 分母 r の積が a 以下となるよ…

AtCoder ABC 070 D - Transit Tree Path (400 点)

一見、ツリー上のパスクエリ (オイラーツアーとかするやつ) な問題に見えるけど、そんなことはなかった 問題へのリンク 問題概要 頂点のツリー (辺に重み付き) が与えられる。ツリー上の 1 点 が与えられて、以下のクエリに 個答えよ: クエリ (): から を経…

AOJ 0613 財宝 (JOI 2014 予選 F)

スライド最小値の練習 問題へのリンク 問題概要 個のアイテムがって、それぞれ市場価値 と貴重度 が与えられる。 今、A さんと B さんがそれぞれアイテムのうちの何個かをとる。このとき、A さんと B さんは同じアイテムを取ることはできず、2 人ともとらな…

AISing Programming Contest 2019 C - Alternating Path (300 点)

DP とかメモ化再帰とか考え出すとドツボにはまる...素直な考察が大事だね。 問題へのリンク 問題概要 H × W のグリッドが与えられる。各マスは白か黒で塗られている。「黒」マスと「白」マスのペアであって、 黒マスから出発して、隣接するマスを辿っていく…

2018 codeFlyer 本選 E - 数式とクエリ (700 点)

構文解析、超絶苦手系だけど苦手とばかり言っていられない。 問題へのリンク 問題概要 (a)*a+((a+(a*(a))-(a)*a+a*a))*a のような文字列 が与えられる。各 a に入るデフォルトの数値 が与えられている。今 個のクエリが来て、各クエリは : 個目の a を で置…

Codeforces Educational 046 E - We Need More Bosses

二重辺連結成分分解と聞いて 問題へのリンク 問題概要 n 頂点 m 辺の連結な無向単純グラフが与えられる。2 点 s, t を選んで、「その辺を壊したら s と t とが繋がらなくなる」ような辺をすべて壊すことを考える。できるだけ多くの辺を壊したい。うまく s, t…

AtCoder ARC 099 E - Independence (700 点)

いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たいのん。こういうのを素早く通せるようになりたいん。 類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷…