2021-03-01から1ヶ月間の記事一覧
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1945 (記事作成時点) 供養 解法 元のグラフを $G = (V, E)$ とする パス $v_{1}, \dots, v_{N}$ が回文になるということは、$v_{1}$ および $v_{N}$ からそれぞれ同じ…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 供養 解法 $v_{i}, w_{j}$ 間に重み $B_{v_{i}, w_{j}}$ の辺がある二部グラフ $G = (V, W, E)$ を考える $B_{v_{i}, w_{j}} = 0$ のとき、$v_{i}, w_{j}$ 間に辺はないものとする…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1650 (記事作成時点) 供養 解法 $f_{k}(f_{k - 1}( \dots f_{1}(x) \dots ))$ を表す関数を $F_{k}(x)$ とすると、$F_{k}$ は3つのパラメータ $y_{k}, z_{k}, w_{k}$ …
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 2068 (記事作成時点) 供養 解法 任意の $A \le n \lt m \le B$ について、 $\mathit{GCD}(n, m) = \mathit{GCD}(n, m - n) \le m - n \le B - A$ である 従って、ある…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 779 (記事作成時点) 供養 解法 0 を $N$ 個、1 を $N$ 個、0 を $1$ 個の順に並べた01列は任意の $S_{i} + S_{i}$ の部分文字列となる $N$ 個目の 0 の出現位置を $j$…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1895 (記事作成時点) 供養 解法 グラフの頂点集合 $V$ の部分集合 $S$ および $S$ からなる $G$ の誘導部分グラフ $G(S)$ についてこの問題を解いた場合の解を $\math…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 2197 (記事作成時点) 供養 解法 $N$ を最上位の桁が0でない $L$ 桁の $d(=16)$ 進数とする $\mathit{DP}_{l, k}$ を以下の条件を満たす $d$ 進数 $H_{l}$ のパターン…