2021-07-27から1日間の記事一覧
AtCoder
AtCoder400点
ABC-D
水色diff
ギリギリ
最適化テク:端点のみを考える
最適化テク:解を変形していく(最適性を失わずに)
二次元平面上のN点の問題
二次元累積和
全探索
制約条件:長方形領域
最適化テク:探索候補を絞る
計算幾何
WaveletMatrix
区間の長さの最大値または最小値を求める
古き良き全探索問題!! 問題へのリンク 問題概要 二次元平面上に 個の点があります。 番目の点の座標を とします。 この二次元平面上で各辺が X 軸・Y 軸に平行であるような長方形であって、 個の点のうち 個以上の点を内部および周に含むようなものを考え…
AtCoder
AtCoder300点
緑色diff
ABC-C
グラフ
DFS
BFS
Union-Find
連結成分
非自明な線形時間
二重辺連結成分分解・二重頂点連結成分分解
各kに対して
グラフのconnectivity
クエリ:削除
けんちょん本演習問題
N個のものうち1個を変更・削除したものを解く
【問題集】DFS・BFSのステップアップ
グラフの橋
Union-Find や、DFS、BFS などで解ける問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフ が与えられます。 グラフ の辺 が橋であるとは、その辺を除去したときに、グラフが連結でなくなることを指すものとします。 グラフ におい…