Edit

【pythonでABC192を解説】F - Potion

問題概要

問題ページ

F - Potion
F - Potion

問題ページへ移動する

問題文

\(N\) 種類の素材があり、素材 \(i\) には \(A_i\) の魔力があります。

魔法使いの高橋君は、この中から \(1\) 種類以上を選んで合成し、ポーションを作ろうとしています。

\(k\) 種類の素材を合成して出来たポーションの魔力は、合成した直後には素材の魔力の合計であり、時間が \(1\) 経過するごとに \(k\) 増加します。
魔力の増加は連続的ではなく離散的であることに注意してください。

高橋君が時刻 \(0\) に \(1\) 度だけ素材の合成を行うとき、魔力がちょうど \(X\) のポーションは、最速でいつ手に入りますか？

なお、制約下で魔力がちょうど \(X\) のポーションを作れることが証明されます。

制約

  • \(1 \leq N \leq 100\)
  • \(1 \leq A_i \leq 10^7\)
  • \(10^9 \leq X \leq 10^{18}\)
  • 入力は全て整数

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, x = list(map(int, input().rstrip('\n').split()))
    a = sorted(list(map(int, input().rstrip('\n').split())), reverse=True)
    ls = [[0] * 1000 for _ in range(n + 1)]
    mn = 10 ** 30
    for i in range(1, n + 1):
        xd = x % i
        ls = [[0] * i for _ in range(i)]
        for v in a:
            for j in range(i - 1, -1, -1):
                if j == 0:
                    ls[j][v % i] = max(ls[j][v % i], v)
                else:
                    for k in range(i):
                        if ls[j-1][k] != 0:
                            p_v = (ls[j-1][k] + v) % i
                            ls[j][p_v] = max(ls[j][p_v], ls[j-1][k] + v)
        if ls[-1][xd] != 0:
            mn = min(mn, (x - ls[-1][xd]) // i)
    print(mn)


if __name__ == '__main__':
    solve()

-Edit
-