TopCoder SRM 657 Div1 Easy: ProblemSets, Div2 Med: ProblemSetsEasy

朝SRMだったが参加できず。Easyは自力で解けて194ptほど。本番なら150番くらいでほんの少しレーティングが上がるくらいの成績。

問題

コンテストに出す問題セットを作っている。コンテストはEasy,Medium, Hardの３つの難易度からなる。用意している問題はEasy用、EasyかMedium用、Medium用、MediumかHard用、Hard用の５種類あり、それぞれE, EM, M, MH, H個ある。作ることの出来る問題セットの数の最大値を答えよ。
max(E, EM, M, MH, H) ≦ 10000 (Div2), 10¹⁸(Div1)

解法

Div2の制限ならシミュレーションで解くことができる。Div1は制限が大きいので同様の解法は無理だが、二分探索を用いれば解くことができる。

m個の問題セットを作れると仮定した時に、実際その数だけ作れるかどうかで右または左の探索範囲を狭めていく。

def maxSets(self, E, EM, M, MH, H):
    l, r = -1, 10**30
    while r - l > 1:
        flag = True
        m = (l + r) / 2
        if E + EM < m: flag = False
        if H + MH < m: flag = False
        if M + max(0, EM - max(0, m - E)) + max(0, MH - max(0, m - H)) < m: flag = False
        if flag:
            l = m
        else:
            r = m
    return (l + r) / 2

Div2でのシミュレーション解法は下になる。

def maxSets(self, E, EM, M, MH, H):
    ans = 0
    while min(E + EM, H + MH) > 0:
        E -= 1; M -= 1; H -= 1;
        ans += 1
        if E == 0 and EM > 0:
            E += 1; EM -= 1
        if H == 0 and MH > 0:
            H += 1; MH -= 1
        if M + EM + MH <= 0:
            break
    return ans