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