はじめに この記事でやること この記事でやらないこと 1. ZDD の概要 1.1. ZDD とは 1.2. ZDD の基礎的な構成方法 1.3. ZDD の効率的な構成方法 1.3.1. 部分集合族の分解 1.3.2. 圧縮規則の再帰的な適用 1.3.3. ハッシュ関数 2. 実装 2.1. RollingHash クラ…

はじめに Daily Akari というパズルがあります。 dailyakari.com ルールを見た瞬間、ZDD で解けるなぁと思ったので、解きました。 ZDD が何かについては、過去記事を参照してください。(全3部) 過去記事↓ ZDDと8-Queen problemの話【卒研お勉強枠①】 - 競プ…

はじめに 鳩が 匹と鳩の巣が 個あり、各鳩はいずれか一つの巣に入っているとします。このとき、 ならば、必ず 匹以上の鳩が入った巣が存在します。あたりまえ体操ですね。この主張を、鳩ノ巣原理と呼びます。 この鳩ノ巣原理、競プロでたまーに出てきては猛…

はじめに この記事でやること 問題概要 解法解説 クエリごとの解法について 判定問題を並列に解く 実装例 おわりに PyPyでもちゃんと通る解法（2024/1/15 追記） はじめに 前回の記事 で並列二分探索というテクニックについて触れましたが、ABC388 にてつい…