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

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

最小カット

AOJ 2872 最短距離を伸ばすえびちゃん (RUPC 2018 day3-F)

「最短路に含まれる可能性のある辺を列挙する」という考え方と、最小カットを組み合わせます。教育的な良問といえますね。 問題へのリンク editorial なお、この問題の設定を少し変えると非常に難しい問題が得られることも知られています (難しい問題: AOJ 2…

AtCoder ABC 010 D - 浮気予防 (青色)

最小カットのよい練習問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられます。頂点番号を とします。また、頂点 0 以外の 個の頂点 が与えられます。 今、次の操作を行っていくことで、頂点 0 からは頂点 のいずれにも到達で…

AtCoder ARC 074 F - Lotus Leaves (黄色, 800 点)

見るからに最小カットだけど、こういうの意外と詰め切るのに時間がかかるイメージがある... 問題へのリンク 問題概要 の二次元グリッドが与えられる。各マスは 'S' のマス:カエルがいる 'T' のマス:カエルがそこにいきたい 'o' のマス:葉っぱがある '.' …

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

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

早稲田大学プログラミングコンテスト WUPC 2019 F - RPG

フロー大好き!!!!!!!! 問題へのリンク 問題概要 頂点 辺の DAG が与えられる。頂点 からスタートして頂点 へと向かいたい。すべての頂点 に対し、 から へと向かうパスと、 から へと向かうパスが存在することが保証されている。 頂点のうちいくつか…

AOJ 3058 Ghost (RUPC 2019 day2-H)

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

AOJ 2903 Board (AUPC 2018 day1-H)

燃やす埋めるを本気で整理する!!! すごく面白い問題だった!!! 問題へのリンク 問題概要 × の二次元ボードが与えられる。以下のような "#" のところを最小個数の長方形で敷き詰めよ。例えば 4 10 ########## ....#..... ....#..... .......... は下のよ…

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

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