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

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Educational Codeforces Round 8 F. Bear and Fair Set

SRM680 div1easy と同様の手段で解こうと頑張っていたが、結局フローで通した。

codeforces.com

解法

次のようなグラフを作って流す。interval - mod 間の辺は省略している。

f:id:pekempey:20160222171906p:plain

  • mi は区間で使える数の個数。
  • si は区間内にある mod 5 で i になるような数の個数。

最大流が n になれば割り当てる方法があるので fair、そうでなければ unfair。

Submission #16273007 - Codeforces

Educational Codeforces Round 8 F. Bear and Fair Se ...


集合 {0,1,2,3,4} の冪集合に属する任意の集合を A に対して、A の要素をなるべく少なく選んだときの個数が |A|*n/5 以下であるか判定するだけでも通った。 本当に正しいのかは分からない。

Editorial には Hall の結婚定理と書いてあったが、どのように定理を使っているのだろう? SRM680 div1easy の判定法を一般化するとこうなる程度の理解しかできなかった。

Submission #16273520 - Codeforces

制約が緩かったためフローが想定解だと一瞬思ったが、やはり頭のいい解法があった。 本当は Hall の結婚定理まで解説が書きたかったが、分からなかったので中途半端な書き方になってしまった。