コンテストでの時間切れや解けなかった過去問を振り返って供養していく 問題 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} -…
前の記事にも書いた通り新しいオモチャ端末を入手したので、ついでに開発環境も色々新しくしてみた。 Poetry ぶっちゃけ今までPythonのパッケージ管理などしてこなかったのだが、まあ折角なので何か入れてみようと思い、 調べて名前が挙がったのが Pipenv/Po…
会社で使っている検証端末を買い替えてもらった。 新しい端末をセットアップするときは環境知識をアップデートするチャンスなので、これ幸いとばかりに試した結果をメモしておく。 TL;DR Preztoを導入した GNU系コマンドを入れた asdfを導入した Homebrew な…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 8/2: AtCoder beginner Contest 174 F - Range Set Query 供養 問題 Difficulty: 1575 (記事作成時点) 解法 の順に見ていき、各色 について最後に登場した位置 を記録しておく BITを用…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 7/5: AtCoder Beginner Contest 173 F - Intervals on Tree 供養 問題 Difficulty: 1806 (記事作成時点) 解法 連結成分の数 頂点数 辺の数となる 頂点と辺をそれぞれ独立に、自分が含ま…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 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) (記事作成時点) 解法 一般性を失わず とする について ならば条件を満たすように を振…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 6/8: AtCoder Grand Contest 045 A. Xor Battle 供養 問題 Difficulty: 1776 (記事作成時点) 解法 を後ろから見ていって、 1 のとき、それまでに見た 0 であるような を任意に組み合わ…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 6/1: AtCoder Regular Contest 039 D - 旅行会社高橋君 供養 問題 Difficulty: 2430(estimated) (記事作成時点) 解法 グラフを二辺連結成分に分解する DFSをしながら各点 の深さ を求め…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 5/22: AtCoder Regular Contest 050 D - Suffix Concat 供養 問題 Difficulty: 2405(estimated) (記事作成時点) 解法 任意の について であるという関係が成り立つように をソートする …
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 5/15: AtCoder Regular Contest 052 D - 9 供養 問題 Difficulty: 2355(estimated) (記事作成時点) 解法 十進表記した の各桁の和を としたとき、 より であればよい としたとき、 と表…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 5/8: Donutsプロコンチャレンジ2015 D - ドーナツの箱詰め 供養 問題 Difficulty: 2310(estimated) (記事作成時点) 解法 箱 について、 である および、 である を使用可能な箱から選ぶ…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 5/1: AtCoder Regular Contest 026 D - 道を直すお仕事 供養 問題 Difficulty: 2259(estimated) (記事作成時点) 解法 時給 を固定したときに採算がとれるかを調べる より が言える の辺…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 4/22: DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選 C - 特別講演「括弧列と塗り分け」 供養 問題 Difficulty: 2162(estimated) (記事作成時点) 解法 …
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 4/15: AtCoder Regular Contest 046 C - 合コン大作戦 供養 問題 Difficulty: 2104(estimated) (記事作成時点) 解法 を について昇順に、 であるような から かつ が最小の と組むよう…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 4/8: AtCoder Regular Contest 030 C - 有向グラフ 供養 問題 Difficulty: 2076(estimated) (記事作成時点) 解法 同じ強連結成分の文字は任意の順番で拾えるので辞書順で小さい順に拾っ…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 4/1: CODE FESTIVAL 2014 決勝 F - 誤情報 供養 問題 Difficulty: 2028(estimated) (記事作成時点) 解法 矛盾がない状態のとき、任意の は で割り切ることができる は の最大公約数であ…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 3/22: AtCoder Grand Contest 043 B - 123 Triangle 供養 問題 Difficulty: 1982 (記事作成時点) 解法 において は の3通りだけしか出てこない 偶奇だけに着目すると、 に等しくなる に…
