TopCoder SRM 680 (Div. 1) Easy. BearFair
DP 解は考えれば分かると思うので O(B) 解の方を書いておく。
解法
以下の値を求める。
- minEven := 偶奇を無視して要素を持ってくるとき、持ってこれる偶数の個数の最小値
- maxEven := 偶奇を無視して要素を持ってくるとき、持ってこれる偶数の個数の最大値
これらを使うと次のように判定できる。
- 矛盾する条件を含んでいる場合は unfair。
- 偶奇を無視しても n 個持ってこれない場合は unfair。
- minEven≦n/2≦maxEven の場合は偶数と奇数をそれぞれ n/2 個ずつ選ぶ方法が存在するので fair、そうでなければ unfair。
TopCoder SRM 680 (Div. 1) Easy. BearFair
この問題が同様の手段で解けるという噂を耳にしたので解いてみた。
code-festival-2014-qualb.contest.atcoder.jp
言われてみればなるほどと思う解法。
