コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1341 (記事作成時点) 供養 解法 ある連結成分で最も重みの大きな辺を $uv$、重みを $w$ として、連結成分を $uv$ で分割したときに $u$ が所属する側の点集合を $U$、…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 2332 (記事作成時点) 供養 解法 時刻 $t$ に起こりうるアクションとその順番を固定するために以下のように時刻を変更した操作列を作る 時刻 $3S_{i} + 2$ にバス $i$ …

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 供養 解法 $v_{i}, w_{j}$ 間に重み $B_{v_{i}, w_{j}}$ の辺がある二部グラフ $G = (V, W, E)$ を考える $B_{v_{i}, w_{j}} = 0$ のとき、$v_{i}, w_{j}$ 間に辺はないものとする…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 6/1: AtCoder Regular Contest 039 D - 旅行会社高橋君 供養 問題 Difficulty: 2430(estimated) (記事作成時点) 解法 グラフを二辺連結成分に分解する DFSをしながら各点 の深さ を求め…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 5/1: AtCoder Regular Contest 026 D - 道を直すお仕事 供養 問題 Difficulty: 2259(estimated) (記事作成時点) 解法 時給 を固定したときに採算がとれるかを調べる より が言える の辺…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 4/15: AtCoder Regular Contest 046 C - 合コン大作戦 供養 問題 Difficulty: 2104(estimated) (記事作成時点) 解法 を について昇順に、 であるような から かつ が最小の と組むよう…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/22: AtCoder Grand Contest 014 D - Black and White Tree 供養 問題 Difficulty: 2293 (記事作成時点) 解法 木 が完全マッチング可能な場合かつその限りにおいて後手が勝つ ある完全…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/8: AtCoder Regular Contest 025 C - ウサギとカメ 供養 問題 Difficulty: 2258(estimated) (記事作成時点) 解法 について、 を始点とする各点への最短路を探索し、 である各点への最…

概要 グラフの連結成分について調べるために使用する Union()関数とFind()関数からなる 連結成分同士の結合をUnion()関数で実施する 同じ連結成分に属する頂点はFind()関数で同じ代表点が返ってくる Find()関数で経路圧縮すると、ならし計算量がAckerman関数…