ABC138 C - Alchemist

備忘録

問題

atcoder.jp

回答

import sys
import os


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

    N = int(sys.stdin.buffer.readline().rstrip())
    V = list(map(int, sys.stdin.buffer.readline().split()))
    V.sort()

    for n in range(N-1):
        V[n+1] = (V[n] + V[n+1])/2

    print(V[N-1])


if __name__ == '__main__':
    main()

考え方

2個(x, y)の食材を鍋に入れると(x + y) / 2 = (x/2 + y/2)の価値になる。
仮にx = 100とすると、1回の生成で100/2、2回目の生成で100/4となり、
他の食材と混ぜて別の食材に生成されるたびに、価値が半減していく。
そのため、価値の高い食材は最後に混ぜ、
価値の低い食材から他の食材と混ぜていくことで、最も高い価値を求めることが出来る。