drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder400点 unrated公式コン フロー グラフ 二次元グリッド 二部グラフ 最大安定集合・最小点被覆・最小辺被覆 マッチング 二部マッチング 考察：パリティに着目する 市松模様・塗り分け けんちょん本演習問題 最大安定集合問題 NP困難(特殊構造なので解ける) そのまま覚えたい典型問題 【問題集】フローの入門 駒(コマ)や石やコインを扱う問題 NoviSteps3D 「二部グラフの最大安定集合問題」について知っていれば典型問題ですね。 問題へのリンク 問題概要 のグリッドがあります。各マスは白黒に塗られています。今、白いマスにできるだけ多くのコマを置きたいものとします。 各マスに 1 個のみコマを置ける コマを置けるのは白いマスのみである 隣り合う白マスの双方にコマを置くのは禁止である という制約下で最大何個のコマを置けるかを求めてください。 制約 最大安定集合問題 まずそもそもこの問題は、「グラフの最大安定集合問題」そのものの形をしています。最大安定集合問題とは、下図のように「頂点のなかから、どの 2 頂点も辺で結ばれていないようにいくつかの頂点を選ぶと… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2019%2F06%2F17%2F221400" title="SoundHound 2018 予選 C - 広告 (3D, 400 点) - けんちょんの競プロ精進記録" 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/80936665/1516148889515660 Hatena Blog https://hatena.blog 2019-06-17 22:14:00 rich https://drken1215.hatenablog.com/entry/2019/06/17/221400 1.0 100%