ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Dinic法(最大流,最小カット)

AGC037 D - Sorting a Grid

問題 提出コード 解法 当たり前ですが、ある数字を取ってくると、最終的にどの行、どの列にいるべきか、というのが決まっています。 そこから逆算すると、3回目の操作開始時点では、 全ての数について、いるべき行は正しい という条件が成り立っていればよい…

ACM-ICPC Japan Alumni Group Summer Camp 2019 Day 1 - J Rooks Game

問題 問題概要 の盤面に、個の駒が配置されています。それぞれの駒は、縦か横方向に好きなだけ移動させることができ、他の駒にぶつかったら、その時点で停止してぶつかった駒を獲得することができます。ただし、他の駒が存在しない方向へ動かすことはできま…

AOJ 1163 - カードゲーム

問題 提出コード 解法 フローの典型っぽいマッチング問題です。 始点、終点と、赤青のカードそれぞれを表す頂点を用意し、始点→赤の頂点、青の頂点→終点に重み1の辺を張っておきます。 そして、任意の赤と青のカードのペアについて、取り除くことができるも…

AOJ 3058 - Ghost (RUPC2019 Day2 H)

問題 提出コード 解法 燃やす埋める問題です。 詳しくはこちらを。 始点と終点および各幽霊に対応する作り、から各幽霊、各幽霊からに辺をはります。 この際、から出てくる辺を左に向くパターン、へ向かう辺を右に向くパターンとすると、 今番目の幽霊が向い…

WUPC2019のお話(解法編)

ということで、今回は各問題についての簡単な解法と、その感想です。 まだ解けていない問題もいくつかあるので、ご容赦ください… 運営側としてどんなことをしたか、についてはこちらの記事をご覧ください。 emtubasa.hateblo.jp 各問題の方針と感想 A - WAse…

ARC085 E - MUL

問題 提出コード 解法 燃やす埋める問題の応用です。 燃やす埋める問題についてはこちらを参考にするといいかと思います。 最小カットを使って「燃やす埋める問題」を解く 今回は、燃やす→売る、埋める→売らない、というようにして帰着させます。 s,tという2…

AOJ 3047 - Shiritori

問題 提出コード 解法 ある文字が最後の1文字となるには、ある文字が先頭となっている単語をすべて使い切った上で、その文字が最後の文字となっている単語にいきつくことが必要になります。 a~zまでの文字をそれぞれ頂点としたグラフを考えます。すべての単…

ABC009 D - 浮気予防

D - 浮気予防 提出コード 最小カットの問題に初めて触れました。 まずは、女の子と高橋君を頂点、友人関係を辺としたグラフを作成します。 そして、頂点0からへ繋がるパスが存在しなくなるような辺の切り方を考えることになります。 ここで、複数のゴールが…