けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

マトロイドと劣モジュラ関数

AtCoder ABC 326 G - Unlock Achievement (橙色, 625 点)

2 変数劣モジュラ関数の和の最小化を最小カットにするやつ! 問題へのリンク 問題概要 種類のスキルがある。それぞれ初期状態のスキルレベルは 1 であるが、最大で 5 まで上げられる。スキル のスキルレベルを 1 上げるのに必要なコストは 円である。 種類の…

AtCoder ABC 259 G - Grid Card Game (橙色, 600 点)

opt さんの「そのままだと優モジュラ最適化なので、青木君の選ぶ・選ばないをひっくり返せば劣モジュラ最適化。よって最小カットでできる」が賢かった。 競プロで言うところの「燃やす埋める」 問題へのリンク 問題概要 のグリッドがあって、各マス には整数…

AtCoder ARC 085 E - MUL (橙色, 700 点)

いわゆる「燃やす埋める」の典型です。 問題へのリンク 問題概要 個の整数 が与えられます (負値もありえます)。今、各 に対して、以下の操作を行うか行わないかを選んで行うことができます。 番目の操作: の倍数であるようなすべての に対して、 の値を 0 …

AOJ 3058 Ghost (RUPC 2019 day2-H)

燃やして埋めます。後日ちゃんと詳しくまとめて解説書こうと思う。取り急ぎ。。。 問題へのリンク 問題概要 長さ の文字列 が与えられる。文字列は 'L' と 'R' で構成されている。文字列の "恐怖度" を以下のように定義する。 個の index ペア ui, vi (ui < …

AOJ 2903 Board (AUPC 2018 day1-H)

2 変数劣モジュラ関数の和を最小カットで表すという、とても面白い問題!!! 問題へのリンク 問題概要 × の二次元ボードが与えられる。以下のような "#" のところを最小個数の長方形で敷き詰めよ。例えば 4 10 ########## ....#..... ....#..... ..........…

AOJ 2943 イルミネーション (RUPC 2019 day1-G)

燃やす埋めるは今度こそちゃんとマスターする!!! 問題へのリンク 問題概要 × の各格子点に電球がある。 が偶数となるような について、 を頂点とする正方形の中心に装置があって、各装置を押すことで四隅の電球を点灯することができる。 ただし、装置を起…