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

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

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

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

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 6/22: AtCoder Grand Contest 046 C - Shift 供養 問題 Difficulty: 2084 (記事作成時点) 解法 中の 0 の数を とすると、問題は 個の 1 を 個の区間に配置した初期状態から、1つ選んで…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 6/15: AtCoder Grand Contest 009 C - Division into Two 供養 問題 Difficulty: 2457(estimated) (記事作成時点) 解法 一般性を失わず とする について ならば条件を満たすように を振…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 4/22: DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選 C - 特別講演「括弧列と塗り分け」 供養 問題 Difficulty: 2162(estimated) (記事作成時点) 解法 …

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 4/8: AtCoder Regular Contest 030 C - 有向グラフ 供養 問題 Difficulty: 2076(estimated) (記事作成時点) 解法 同じ強連結成分の文字は任意の順番で拾えるので辞書順で小さい順に拾っ…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 3/22: AtCoder Grand Contest 043 B - 123 Triangle 供養 問題 Difficulty: 1982 (記事作成時点) 解法 において は の3通りだけしか出てこない 偶奇だけに着目すると、 に等しくなる に…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 3/15: パナソニックプログラミングコンテスト2020 E - Three Substrings 供養 問題 Difficulty: 2366 (記事作成時点) 解法 を固定したときに の相対的な開始位置を としたとき、矛盾な…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 3/8: diverta 2019 Programming Contest E - XOR Partitioning 供養 問題 Difficulty: 2371 (記事作成時点) 解法 とする である で 個の区間に分割するとする 分割した区間のXORが全て …

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 3/1: AtCoder Grand Contest 024 D - Isomorphism Freak 供養 問題 Difficulty: 2342 (記事作成時点) 解法 もとの木の直径を とすると、少なくとも 色が必要 直径を だけ増加させるよう…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/15: AtCoder Regular Contest 090 E - Avoiding Collision 供養 問題 Difficulty: 2282 (記事作成時点) 解法 - 間の最短距離を取るパス全ての組み合わせから高橋君と青木君が遭遇する…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/1: AtCoder Regular Contest 074 F - Lotus Leaves 供養 問題 Difficulty: 2205 (記事作成時点) 解法 最小カットに帰着する方法と、 間の局所点連結度を求める方法がある 解法1: 最小…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 1/22: AtCoder Beginner Contest 152 F - Tree and Constraints 供養 問題 Difficulty: 1903 (記事作成時点) 解法 条件のどれか1つでも満たさないようなパターンを数える 条件 を満たさ…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 1/15: AtCoder Beginner Contest 151 F - Enclose All 供養 問題 Difficulty: 1698 (記事作成時点) 解法 最小包含円の半径を求める問題 互いに異なるある2点 について、それぞれから距…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 1/1: AtCoder Beginner Contest 149 E - Handshake 供養 問題 Difficulty: Undefined (記事作成時点) 解法 「左手で握手する相手を固定したときに幸福度上昇値が 以上となる右手の相手…

コンテストでの時間切れや解けなかった過去問を振り返って供養していく 12/28: AtCoder Beginner Contest 147 E - Balanced Path 供養 問題 Difficulty: 1656 (2019/12/28現在) 解法 各マス について とする マス の時点で偏り のパスを作れるか、というBool…