atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ Color Coding 乱択アルゴリズム グラフ理論 確率 1. 概要 本記事では，Color-Coding という手法について解説します． Color-Coding とは $k$ 個のものを選ぶというような存在判定問題や最適化問題において，それぞれのものにランダムな色を割り当てるという手法です．特に，比較的小さな $k$ について「ちょうど $k$ 種類のものを $1$ 度ずつ使う必要がある」という制約がある最適化問題で強力です．学術的にはグラフから $k$ 頂点のパスやサイクル，その他の種類の部分グラフを検出するアルゴリズムとして提案された乱択アルゴリズムです（文献 1）． 本記事ではそのうちでも最も簡潔な，パスの検出という問題を通して Color… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fcolor_coding" title="Color-Coding - AtCoderInfo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738 Hatena Blog https://hatena.blog 2026-04-10 14:17:14 rich https://info.atcoder.jp/entry/algorithm_lectures/color_coding 1.0 100%