オンサイトで未確認

ukuku09の活動記録。

AOJ 2370: RabbitWalking

久しぶりにブログを書くわ!自分用メモだけど。

 

問題概要

RabbitWalking | Aizu Online Judge

 

解法

まず"-1"の判定ですが、グラフが奇閉路を含まないことと二部グラフであることは必要十分条件なので、与えられたグラフの各連結成分が二部グラフであるかどうか判定します。もし二部グラフでない連結成分が一つでもあったら"-1"です。

二部グラフ判定はUnionFindやDFSを使って判定できますが、今回は後から各連結成分の各色(ここでは黒と白とします)の個数を利用したいので、DFSで2彩色しながら個数を数えるのが良いと思います。

(後述しますが、正確には各色の個数というより、二部グラフを構成する2つの頂点集合の大きさが必要になります)

 

もしすべての連結成分が二部グラフである場合、辺を0本以上追加して二部グラフを保ったまま各連結成分を連結することができます。

課題から、辺の追加本数を最大化したいので、各連結成分は完全二部グラフにしてしまって良いことが考察できます。さらに、各連結成分を連結してできる二部グラフもまた完全二部グラフにできます。

完全二部グラフの辺の本数は(黒の個数)*(白の個数)なので、結局(各連結成分の黒の個数の和)*(各連結成分の白の和)を最大化すると良さそうです。

 

先ほど各連結成分ごとに適当に2彩色しましたが、連結成分内ですべての頂点の色を反転させても2彩色状態は保たれるので、二部グラフの2つの頂点集合の大きさのみに注目します。

今、いくつかの連結成分を連結してできた完全二部グラフ$K_{n_i,m_i}$と、まだ連結していない連結成分$K_{a_j,b_j}$を連結すると、新たな完全二部グラフとして、$K_{n_i+a_j,m_i+b_j}$または$K_{n_i+b_j,m_i+a_j}$を得ることができます。このようにして得られる完全二部グラフ$K_{n_k,m_k}$における$n_k*m_k$の最大値が求めるべき解です。(あとで元からある辺の数$E$を引きます)

(2つの頂点集合$V_1,V_2$の大きさをそれぞれ$x,y$とする完全二部グラフを$K_{x,y}$と表記しています)

 

これを解くために次のようなDPを考えてみます。

$dp[i][j][k]:=i$番目までの連結成分を用いて$K_{j,k}$を作ることができるか

これを計算すると、$dp[V][j][k]==true$を満たす$j,k$の積の最大値が解となります。

さらに、$k$の最適値は$i$と$j$がわかれば一意に定まるので、$dp[i][j]$としてしまっても良さそうです。しかし、このDPでは計算量が$O(V^2)$になってしまうので当然間に合いません。

 

計算量を落とすためのアイデアとして、各連結成分$K_{a_j,b_j}$における2つの頂点集合の大きさの差分$abs(a_j-b_j)$($c_j$とします)と、$Σmin(a_j,b_j)$($L$とします)を考えます。すべての連結成分を用いてできる完全二部グラフは、どちらの頂点集合の大きさも必ず$L$以上になっているはずです。また、完全二部グラフの$V_1$の大きさの増分はいくつかの$c_j$の和$sum$として表すことができます。全体の頂点数は$V$なので、この完全二部グラフは$K_{L+sum,V-L-sum}$となります。($a_j>b_j$なら、$n_k$に$a_j$を足して$m_k$に$b_j$を足すのは、$n_k$に$b_j+c_j$を足して$m_k$に$b_j$を足すと見なせます)

(補足ですが、求めるべき完全二部グラフは必ずすべての頂点を含んでいます。これは、完全二部グラフの2つの頂点集合の大きさが連結に伴って単調増加するためです)

 

したがって、先のDPは次のように書き直すことができます。

$dp[i][j]:=i$番目までの差分を用いて$j$を作ることができるか

さらに、$c_j$の種類数は$O(√V)$程度に収まるので、個数制限付き部分和問題(詳しくは蟻本P62参照)と見なして$O(V√V)$で解くことができます。

 

gist85ccc57cc00c88617e78bccfb8de48fc

 

すごく冗長、しかも変数や添字が最高にわかりづらいわ…。はぁ〜、なんて悪魔的なのかしらぁ〜!

 

RUPC2017参加記

  • 前置き
  • Day 0: 移動フェーズ
  • Day 1: 立命館セット
  • Day 1.5: 懇親会 & 準備
  • Day 2: 会津セット
  •  Day 2.5: 懇親会
  • Day 3: 北大セット
  • 感想
  • ※お詫び
続きを読む

AtCoder Beginner Contest 007 D: 禁止された数字

問題文

abc007.contest.atcoder.jp

解法

桁DPしてくださいという問題。桁DPがわからない人は pekempey さんの記事がとてつもなくわかりやすいのでそちらを見てください。

pekempey.hatenablog.com

 

AtCoder Beginner Contest 008 D: 金塊ゲーム

問題文

abc008.contest.atcoder.jp

解法

問題文が無駄に長くてわかりづらいが、よくあるやつだと思った。

ある装置を起動させると、その装置を基準に領域が最大4つ(左上・左下・右上・右下)に分割されるので、そのそれぞれについて再帰的に調べていけば良い。

 

 

AtCoder Beginner Contest 006 D: トランプ挿入ソート

問題文

abc006.contest.atcoder.jp

解法

抜き取らないトランプに注目すると、それらは増加数列になっているはずなので、最長増加部分列を求めて全体から引いた数が答え。

 

 

AtCoder Beginner Contest 010 D: 浮気予防

問題文

abc010.contest.atcoder.jp

解法

サンプルのグラフを見ると「あー最小カット」という気分になるので最小カット。最大流-最小カット定理より、最大流のアルゴリズムそのままで最小カットの問題も解ける。

 

 

 

AtCoder Beginner Contest 038 D: プレゼント

問題文

abc038.contest.atcoder.jp

解法

dp[i] := i 番目の箱を最も外側に使う時の最大の入れ子の数 でDPする。しかし、普通にやると、その箱に入る箱を探すのを含めて $O(N^2)$ になってしまう。

DPの遷移は、dp[i] = max{dp[j] | wj < wi かつ hj < hi}+1 なので、w で昇順ソートしておくと、dp[i] = max{dp[j] | j < i かつ hj < hi}+1 となって、あとは hj < hi である箱 j のうちの最大の入れ子が高速にわかれば嬉しくなれる。

[1, hi) の最大値を求める部分に BIT を使うと全体で $O(NlogN)$ にできる。

w が等しい時は、h の降順でソートしておくと、更新の際に w が同じ箱同士が入れ子になるのを防げる(最大値を求める区間を考えるとわかる(語彙力がなかった。