読者です 読者をやめる 読者になる 読者になる

hogloidのブログ

へなちょこ

AOJ 2374 RabbitLunch

概要

日本語なので読んでね
RabbitLunch | Aizu Online Judge


































































解法

O(NlogN),O(Nlog^2N) のやり方もいくつかありますが、O(N) で解くことをオススメします
ヒントはフロー(僕はこれをsnukeに教えてもらった)
かなり面白いので、すぐに見ないほうがいいかも。
見たい人は下までスクロール




















































与えられた条件を二部グラフのフローの形にしてみると、
source-人参(流量は人参の個数)
人参-キウイ(m*n の辺を張る。流量はすべて1)
キウイ-sink(流量はキウイの個数)
の辺を張る。

求める値はこのグラフでの最大フロー
これは最小カットに等しい。

source-人参の辺からK本、キウイ-sinkの辺からL本カットに入れると、
人参-キウイの(M-K)*(N-L)本を切ればよい。

よって、source-人参の辺・キウイ-sinkの辺 を切るときは、流量の小さいものから切っていけばいい。

source-人参の辺の切る数をiとして0...Nまで動かす。
人参-キウイ、キウイ-sink での最小カットは、
X軸にキウイ-sinkの切る辺の数を取ると、
f:id:hogloid:20141115234413p:plain

この2つのグラフを合わせたような感じになる。

キウイ-sinkのグラフは、切る辺は小さい順に並んでいるので、下に凸
人参-キウイのグラフはそもそも直線

となり、和を取ったグラフも下に凸
なので、局所解が大域解になってる

ところで、iを1つ大きくした時、キウイ-sinkのグラフは変わらず、
人参-キウイのグラフは傾きが小さくなる。
このとき、キウイ-sinkの切る数の解は少なくなる方向にのみ動くことがわかる。

よって、iを増やしながら、しゃくとり法をすればいいことが分かる。
ソートをバケツソートで行うと、すべてO(N)

ソースコード
AIZU ONLINE JUDGE: Code Review