drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ マトロイド AtCoder AtCoder600点 ABC-G 橙色diff フロー 二次元グリッド 最小カット:PSP(燃やす埋める) 考察：操作・条件・目的関数を言い換える 最大スコア 最大流問題 最小カット 【問題集】フローのステップアップ そのまま覚えたいシンプル設定の中堅以上の典型問題 解空間:O(2^N)通りの選択肢 マトロイドと劣モジュラ関数 最適化問題 NoviSteps3D opt さんの「そのままだと優モジュラ最適化なので、青木君の選ぶ・選ばないをひっくり返せば劣モジュラ最適化。よって最小カットでできる」が賢かった。 競プロで言うところの「燃やす埋める」 問題へのリンク 問題概要 のグリッドがあって、各マス には整数 が書かれている (負数もある)。 今、横何列かと、縦何列かを選んで色を塗る。色が塗られたマスに書かれた整数の総和を最大化したい。 ただし、ある負数のマスが存在して、横方向からも縦方向からも選ぶような状態は禁じる。 制約 考えたこと いかにもフローっぽい。最小カットに帰着できそうな雰囲気を感じるので、簡単のため、最初に をすべて -1 倍して、最小コ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F05%2F04%2F010600" title="AtCoder ABC 259 G - Grid Card Game (3D, 橙色, 600 点) - けんちょんの競プロ精進記録" 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 2023-05-04 01:06:00 rich https://drken1215.hatenablog.com/entry/2023/05/04/010600 1.0 100%