コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1804 (記事作成時点) 供養 解法 連結成分が異なる場合独立して計算できるので、以降は同一連結成分内で考えるものとする 頂点番号が小さい順に、各頂点が利用できる色…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1161 (記事作成時点) 供養 解法 頂点1からDFSをする それまでの経路上で登場した色を管理しておき、$C_{x}$ が初登場なら $x$ は出力される 出力するか否かのbool配列…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 Difficulty: 1224 (記事作成時点) 供養 解法 文字種が11種類以上ある場合は自明に UNSOLVABLE 各文字に対する数字の割り当てを全通り試して成立するパターンを探す DFSなどで実装…

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

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 02/06: AtCoder Beginner Contest 191 C - Digital Graffiti Difficulty: 1063 (記事作成時点) 供養 解法 左上から見ていって外周上にある点を見つける 自分がどの点の、上下左右どの辺…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 01/23: AtCoder Beginner Contest 189 C - Mandarin Orange Difficulty: 565 (記事作成時点) 供養 解法1 $i = 1, \dots, N$ について、皿 $i$ を含み $A_{i}$ を最小値とするような選び…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 11/2: AtCoder Beginer Contest 178 E - Dist Max 供養 問題 Difficulty: 1043 (記事作成時点) 解法 マンハッタン距離の式を式変形すると以下のようになる \begin{array}{ll} &|x_{i} -…