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

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

フロー

AOJ 3215 Construction Set (OUPC 2020 G)

二部マッチングの復元にてこずって、間に合わなかった... 問題へのリンク editorial 問題概要 個の正の整数 の部分集合であって、以下の条件を満たすもののうち、要素数が最大のものを 1 つ求めよ。 どの要素も 6 で割ったあまりが 1 ではない どの要素も約…

AOJ 2304 Reverse Roads (JAG 夏合宿 2011 day3-E) (450 点)

最大流問題の構造についての理解を問ういい感じの問題! 問題へのリンク 問題概要 頂点数 、辺数 の単純有向グラフが与えられる (すべての辺の容量は 1)。2 点 間の最大フロー (辺素パスの本数) について考える。 今、いくつかの辺を選んで向きを反転するこ…

AOJ 2679 Decoding Ancient Messages (JAG 春コン 2014 C) (700 点)

多倍長整数を活用した、重み付き二部マッチング 問題へのリンク editorial 問題概要 のグリッドが与えられる。各マスにはアルファベット (英大文字と英小文字) が描かれている。今、次の条件を満たすように 個の文字を抜き出す 各行から選ぶマスはちょうど 1…

AOJ 3168 Capture Ebichan (HUPC 2020 day1-E)

アルファベットは 26 文字!26 は偶数! 問題へのリンク 問題概要 (意訳) 頂点数 、辺数 の無向単純グラフ が与えられる。各頂点 には、1 文字の英小文字 が振られている。ここで正の整数 が与えられ、改めて次のように定義されるグラフ を考える の頂点集合…

ACL Contest 1 C - Moving Pieces (青色, 600 点)

フローって確かに天才パズルな問題はすごく天才的なんだけど、典型的な問題もたくさんある! 問題へのリンク 問題概要 下図のような の盤面が与えられる。盤面は通路 ('.') と壁 ('#') がある。いくつかの通路にはコマ ('o') が配置されている。 コマは下方…

AOJ 3183 Flipping a Path (HUPC 2020 day3-L)

こういう系すごく楽しいよね 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向単純グラフ が与えられる。 このグラフ上で次の条件を満たすパス (同じ頂点を二度通らないものに限る) が存在するかどうかを判定し、そのようなパスの重みの最小値を求めよ…

AOJ 2581 完全順列 / Derangement (RUPC 2014 day3-G)

今の RUPC / AUPC の先駆けとなった合宿の北大セットの問題!!! このセットは、全問題のタイトルの頭文字が 'D' というセットだった セットへのリンク 北大アーカイブへのリンク 問題へのリンク 問題概要 長さ の順列 が与えらえる。これらを並び替えて完…

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

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

Educational Codeforces Round 80 F. Red-Blue Graph (R2900)

需要供給を考え、さらに最小流量制約もある最小費用フロー!!! 問題へのリンク 問題概要 左頂点数 、右頂点数 、辺数 の二部グラフが与えられる。各頂点は「赤」または「青」または「白」に塗られている。 さて、各辺は最初は白色である。そのうちの何本か…

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

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

SoundHound 2018 予選 C - 広告 (400 点)

ちょっと話題になった超典型フロー 問題へのリンク 問題概要 のグリッドがあります。各マスは白黒に塗られています。今、白いマスにできるだけ多くのコマを置きたいです。 各マスに 1 個のみ コマを置けるのは白いマスのみ 隣り合う白マスの双方にコマを置く…

AtCoder AGC 032 D - Rotation Sort (橙色, 1000 点)

本番フローで無理矢理解いた!!! でも DP が本筋だね。 問題へのリンク 問題概要 の順列 が与えらえる。これを 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる 整数 を選んで区間 [ ) を右シフトする、…

早稲田大学プログラミングコンテスト 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)

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

AOJ 1163 カードゲーム (ICPC 国内予選 2009 E) (400 点)

高速な二部マッチング、Hopcroft-Karp 法を整備した 問題へのリンク 問題概要 N 枚の赤いカードと、M 枚の青いカードとの間で最大マッチングを作りたい。 各カードには整数値が書かれていて、最大公約数が 1 より大きいカード同士をペアにすることができる。…

いずれちゃんと解きたい、やばいグラフ変形系問題やフロー系問題たち

「グラフを変形して、〜となる最小量を求めよ、〜とならない最大量を求めよ」系はヤバイ問題の宝庫というイメージがあり、それらをいつかやるリストとして挙げてみる。 完全に備忘録 AOJ 2230 How to Create a Good Game DAG があたえられて、2 点 s-t 間の …

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

ABC 051 D - Candidates of No Shortest Paths をやった流れで。この問題なら自然だけど、ちょっと設定変えた問題に超グロ問があったりする (AOJ 2230 How to Create a Good Game)。 問題へのリンク 問題概要 頂点 辺の重み付き有向グラフが与えられる。グラ…

AOJ 3047 Shiritori (AUPC 2018 day3 I)

これはコンテスト本番にて、すぐに解けてよかった 問題へのリンク 問題概要 個の単語 (いずれも英小文字) が与えられる。これらの単語の列が極大しりとりであると は、 しりとりである しりとりの最後尾に続けられる単語がもう残っていない ようなものを指す…

Codeforces Round #511 (Div. 1) B. Little C Loves 3 II (R2200)

なんとか解けてよかった 問題へのリンク 問題概要 × の二次元グリッド盤面が与えられる。 空いているマスを 2 つ選んで、その 2 つに駒を置く。ただしその 2 マス間のマンハッタン距離が 3 でなければならない という操作を繰り返し行う。こうして出来上がる…

POJ 3692 Kindergarten (ARC 099 E の類題として)

ARC 099 E - Independence の類題という感じなん。具体的には「補グラフをとって二部グラフを考えて...」みたいなところのが似てるん。 POJ 3692 Kindergarten 問題概要 G 人の女の子と、B 人の男の子がいて、「女の子同士」「男の子同士」はすべて互いに知…

TopCoder SRM 694 D1H SRMDiv0Easy

二段階単体法のデバッグに苦労しました。 問題概要 初期状態が全要素が 0 であるような N 次元ベクトルに対し、 以下のような Q 個の区間クエリを実施して得られる結果が 全要素が等しい N 次元ベクトルとなるようにしたい。区間クエリ i: 閉区間 [ L[i], R[…