2020-01-01から1年間の記事一覧
前の記事にも書いた通り新しいオモチャ端末を入手したので、ついでに開発環境も色々新しくしてみた。 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通りだけしか出てこない 偶奇だけに着目すると、 に等しくなる に…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 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/22: AtCoder Grand Contest 014 D - Black and White Tree 供養 問題 Difficulty: 2293 (記事作成時点) 解法 木 が完全マッチング可能な場合かつその限りにおいて後手が勝つ ある完全…
概要 あるパラメータをとったときの状態が2値で表せる 更新処理が比較的単純な論理演算で表せる 連続する複数の値を同時に更新できる 上記のようなDPをするときに、いくつかのbitをまとめて数値として計算してしまうことで高速化する、いわゆる定数倍高速化…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/15: AtCoder Regular Contest 090 E - Avoiding Collision 供養 問題 Difficulty: 2282 (記事作成時点) 解法 - 間の最短距離を取るパス全ての組み合わせから高橋君と青木君が遭遇する…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/8: AtCoder Regular Contest 025 C - ウサギとカメ 供養 問題 Difficulty: 2258(estimated) (記事作成時点) 解法 について、 を始点とする各点への最短路を探索し、 である各点への最…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 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/8: AtCoder Beginner Contest 140 F - Many Slimes 供養 問題 Difficulty: 2066 (記事作成時点) 解法 以下の条件を満たす完全二分木を考える 葉に の各要素の値を重複なく持つ 葉以外…
概要 記号列 とパターン が与えられたとき、 と一致する の部分列を探してその位置を返す 部分一致テーブル を事前に計算しておくことで、不一致となったときに次の探索を先頭からではなく途中までは既に部分一致したものとして一部スキップできる（場合があ…
