roiti46's blog

主に競プロ問題の解説を載せてます

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

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

問題はこちら

問題

コンテストに出す問題セットを作っている。コンテストはEasy,Medium, Hardの3つの難易度からなる。用意している問題はEasy用、EasyかMedium用、Medium用、MediumかHard用、Hard用の5種類あり、それぞれE, EM, M, MH, H個ある。作ることの出来る問題セットの数の最大値を答えよ。
max(E, EM, M, MH, H) ≦ 10000 (Div2), 1018(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

まとめ

二分探索を思いつけるかどうかの問題。

広告を非表示にする