ABC338 C - Leftover Recipes

atcoder.jp

問題

• N種類の食材があります
• 材料$i$は、$Q_i$あります
• 料理Aと料理Bがあります
• 料理Aを作るのに、材料$i$が$A_i$必要です
• 料理Bを作るのに、材料$i$が$B_i$必要です
• 料理Aと料理Bをあわせて何人前作れる？

成約

• $ 1 \leq N \leq 10$
• $1 \leq Q_i \leq 10^6$
• $0 \leq A_i \leq 10^6$
• $0 \leq B_i \leq 10^6$
• $A_i$のうち1以上のものが1つ以上存在する
• $B_i$のうち1以上のものが1つ以上存在する

思考

• Nが小さい(最大10)のがポイントかなぁ
• Aを何人前作ります！って決めた時、Bが何人前作れる？の判定は、O(N)で確認できるね
• じゃあ、Aを何人前作るか、を全探索して、それぞれのAに対してBが何人前作れるかを見ていけば良いね

コード

N = int(input())
Q_L = list(map(int, input().split()))
A_L = list(map(int, input().split()))
B_L = list(map(int, input().split()))

ans = 0
inf = 10**18
for a_cnt in range(max(Q_L)+1):
    b_cnt = inf
    for i in range(N):
        if Q_L[i] < a_cnt*A_L[i]:
            break
    else:
        for i in range(N):
            if B_L[i] == 0:continue
            b_cnt = min(b_cnt,(Q_L[i]-a_cnt*A_L[i])//B_L[i])
    ans = max(ans,a_cnt+b_cnt) if b_cnt != inf else ans
print(ans)