ABC034 D - 食塩水

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def check(K, X, concentration):
    salt = [w * ((p-X) / 100) for w, p in concentration]
    salt.sort(reverse=True)
    if sum(salt[:K]) >= 0:
        return True
    return False


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    concentration = []
    for _ in range(N):
        w, p = il()
        concentration.append([w, p])

    left, middle, right = 0, 0, 100
    for _ in range(200):
        middle = (right + left) / 2
        if check(K, middle, concentration):
            left = middle
        else:
            right = middle
    print(left)


if __name__ == '__main__':
    main()

考え方

目標とする濃度を設定し、
与えられた食塩水から目標濃度を作ることができるか否かを二分探索で判定する。

作ることができる濃度0 ~ 100の間なので、
最低値を0、最高値を100から二分探索を行なう。

最低値と最高値の中央値を、目標とする濃度に設定し、
目標濃度の食塩水を作ることができるか判定を行う。

# 食塩水wグラム, 濃度pパーセント, 目標濃度Xパーセントのとき
# 目標濃度に必要な食塩は
w * ((p-X) / 100)
# で求めることができる
# (値が負の時は食塩が足りない、正の時は食塩が余っている)

目標濃度が作れる場合には、最低値を中央値で更新し、
作れない場合には、最高値を中央値で更新することで、作ることができる最高の濃度を特定できる。
上記の二分探索を200回も行えば十分に濃度の特定を行うことができる。

ちなみ、for _ in range(200):をwhile right - left > 0.00001:にしてもACできた。
Submission #14476999 - AtCoder Beginner Contest 034