コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1824 (記事作成時点) 供養 解法 $\max(A_{1}, \dots, A_{N}) = A_{\max}$ とする $A_{1}, \dots, A_{N}$ を $K$ 回の操作で $x$ の倍数にできるかを以下の方法で判定…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1370 (記事作成時点) 供養 解法 $( (a_{i}, 0), (b_{i}, 1) )$ について、$a_{i} \le A$ であるような線分のみ使用することを考える 簡単のため線分 $( (a_{i}, 0), (…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 2287 (記事作成時点) 供養 解法 各点 $u$ について、クエリ $i$ の時点での色が $x$ であったとする $C_{u} = (x, i)$ と、クエリ $i$ で隣接点に伝搬させた色が $x$ …

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1753 (記事作成時点) 供養 解法 点 $N$ までの任意の最短パス $P$ を求め、$P$ を構成する辺を覚えておく 除外する辺が $P$ に含まれる場合、その辺を除いたグラフで…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1954 (記事作成時点) 供養 解法 $N$ 組のペアを作ったとき、各ペアは必ず偶数と奇数の組である 以降は $A_{i}, B_{i}$ の偶奇が異なることを前提に進める $u$ から始…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 2187 (記事作成時点) 供養 解法 取り出し方が一意に定まるような長さ $k$ の部分列の添字列を $x_{1} \lt \dots \lt x_{k}$ としたとき、先頭と最後に $x_{0} = 0, x_…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1853 (記事作成時点) 供養 解法 ある数 $K$ について、異なる2点の距離の最大値 $D$ が $K$ 以上であるかを考える 2点 $i, j$ の距離が $K$ 以上であるということは $…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1835 (記事作成時点) 供養 解法 $x = 1, \dots , 10^{9}$ について、まだ箱に入れておらず $L_{i} \le x$ であるようなボールの集合を $B$ とする このとき、箱 $x$ …

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

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

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 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}$ から末…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1820 (記事作成時点) 供養 解法 $A_{1}$ から $A_{i}$ までの累積和を $C_{i}$ とする $i \lt j$ および $1 \le k \le N$ について $C_{i} \equiv C_{j}\; (\mathrm{m…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1745 (記事作成時点) 供養 解法 整数 $g \gt 1$ について、整数 $a, b \ge 1$ を用いて $(x, y) = (ag, bg)$ と表せれば最大公約数が $g$ の倍数のペアとなる そのよ…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 2025 (記事作成時点) 供養 解法 $N \gt M + K$ のとき、自明に $0$ $(x, y) = (0, 0)$ から $x = x + 1$ もしくは $y = y + 1$ を繰り返して $(M, N)$ に到達するパタ…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1818 (記事作成時点) 供養 解法 操作を次のように考える $x$ を $x + a$ にする、ここで $a \in \lbrace 0, 1 \rbrace$ である $y$ を $y + b$ にする、ここで $b \in…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1710 (記事作成時点) 供養 解法 基本的には経路探索 時刻 $t$ 以降に辺 $i$ を使って移動する際に最も早く移動できるとき、移動先に到達する時刻は $f(x) = x + C_{i}…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1622 (記事作成時点) 供養 解法 問題をある $X$ が与えられたときに、すべての $K \times K$ 区間の中央値が $X$ 以上であるかを判定する問題にする $S_{x, y}$ を $(…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1856 (記事作成時点) 供養 解法 それまでの手順の列を $S$ とする $t = 1, \dots, N - 1$ の順に位置を決めていく $t$ の現在の位置を $n$ とする $n \ge t$ としてよ…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1159 (記事作成時点) 供養 解法 色ごとに $a_{i}$ を集めた集合をそれぞれ $R, G, B$ とする $R, G, B$ がそれぞれ偶数要素からなる集合であった場合、同じ色同士で適…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1638 (記事作成時点) 供養 解法1 根からEuler Tourをしたときの経路を $S = \dots, v_{i}, \dots, v_{i}, \dots$、$v_{i}$ に最初に訪れた順番と最後に訪れた順番をそ…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1354 (記事作成時点) 供養 解法 $\lbrack l, r \rbrack$ が解体可能なとき、$\lbrack l, r \rbrack$ の奇数番目のビルの高さの和と偶数番目のビルの高さの和が等しい …

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1196 (記事作成時点) 供養 解法 まず $B_{i} = \lfloor \frac{A_{i}M}{N} \rfloor$ とする 不足分の $D = M - \sum B_{i}$ 個について、$B_{i} \times N - A_{i} \tim…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1955 (記事作成時点) 供養 解法 おいしさと人気度の合計を $S^{'}$ としたとき、おいしさを $1 \le y \le N$ に決め打てば人気度も一意に定まり、それらのパターン数 …

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1624 (記事作成時点) 供養 解法1 $(r, c) \to (r - i, c)$ の辺を全て作成すると辺の数が $O(RC^{2})$ となるので、各頂点 $(r, c)$ に対応する頂点 $(r^{'}, c^{'})$…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1814 (記事作成時点) 供養 解法 $(1, \dots, N)$ の部分集合 $S$ について、以下の条件を満たす数列の数を $\mathit{DP}_{S}$ とするbitDPをする 数列が $S$ で構成さ…