コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1495 (記事作成時点) 供養 解法 $a_{1}, b_{1}$ が入った集合の約数をそれぞれ $x, y$ と決め打った時に、それらを約数とするような集合を作れるかは $O(N)$ で計算で…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 2350 (記事作成時点) 供養 解法 簡単のため多角形がすべて長方形の場合を考えると、長方形が $(x_{i, 1}, y_{i, 1}), (x_{i, 1}, y_{i, 2}), (x_{i, 2}, y_{i, 1}), (…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 2143 (記事作成時点) 供養 解法 ある最適解は、任意の $1 \le i \lt N$ について $B_{i} = B_{i + 1}$ もしくは $C_{i} = C_{i + 1}$ の少なくとも一方が成り立ってい…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1570 (記事作成時点) 供養 解法 自明な上界として、隣接する2地点に駅を建て、距離1の線路で繋いだものの最小値がある $U$ とする 距離2以上の線路を、点 $(h, w)$ か…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 供養 解法 各セットの最小値の集合 $A$ と、$A$ の各要素 $a_{i}$ を最小値とするセットの最大値 $b_{a_{i}}$ の集合 $B$ を持っておく $A$ から、$s_{j}$ 以下で最大の $a_{l}$ …

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 2153 (記事作成時点) 供養 解法 任意のアルファベット3文字の文字列に対応する頂点からなる頂点集合 $V$ および、各 $s_{i}$ の先頭3文字に対応する点 $u_{i}$ から末…