Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【yukicoder No.904 サメトロ】証明ができん

サメトロって何でしょう?サメがトロールしてんのか?

No.904 サメトロ - yukicoder

問題

問題文が十分簡易なので略

方針

まず、Sum(Ai) = Sum(Bi)は即分かる。物理とか電気の流量の話で考えてもいいし、もっと抽象的にグラフの話と考えてもいい。

これだけ見て、じゃあこれを満たす値は全部OKなんでしょと早合点して

println!("{}", min(asum,bsum)+1);

を提出すると半分くらいはWAする。たぶんこれをやった人は多いはず。

ここで、Ai,Biが小さいと組み合わせの余裕がなくなって、矛盾するということか?と気づく。

そこで条件を再度確認して、

A1,B1がこの条件を満たす => 全iに対してAi <= Sum(Bk) - Bi

も理解出来る。以降これを「条件」と呼ぶこととする。

しかし解説は、これが同値だと言っている。これが全くわからない。

もっと基本に立ち返って考えると、

これは、例えばasum>=bsumであったとして、この差がdであったとすると、

Ai=x,Bi=x+dとした時に条件(左)が成り立つか?という話になる。

従って、Ai=x,Bi=x+dを実際に加えてみて、条件が成り立つかどうか確かめれば良いのだが、これは、人間一人をノード1つと捉えて、Aiに所属する人間をAj(j!=i)に所属するノードに接続した二部マッチングをすることに等しい。もし、人間一人一人に対して、入った駅と出た駅が違う組み合わせが得られるのであれば、条件(左)を満たす。もちろん、この二部マッチング問題は、時間内に解くことは出来ない。理由は、辺の数が多すぎるからである。

解説は、この問題を解くことと、条件(右)を確かめることが同値だと言っている。

例えば、乗車数の少ない駅と降車数の多い駅を優先的に選択して行くというアルゴリズムでもしかしたらO(N2)で解けるかも知れないとは思ったが、これにしてもはっきりしない。

どう考えたらそうなるのか教えてほしい。

こういうフローを考えれば出来るかも?

ノード数を増やすのではなく、エッジのキャパに駅の流入流出を設定した以下のようなグラフで最大流問題を解けば、O(N3)で一回の判定が出来るかも。この問題ではN=37と小さいので間に合う。

f:id:akiradeveloper529:20191012234149j:plain

その上で、aについて二分探索出来るなら解けると思う。