Educational Codeforces Round 8 F. Bear and Fair Set
SRM680 div1easy と同様の手段で解こうと頑張っていたが、結局フローで通した。
解法
次のようなグラフを作って流す。interval - mod 間の辺は省略している。
- 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 の結婚定理まで解説が書きたかったが、分からなかったので中途半端な書き方になってしまった。