競プロ初中級者100問

ABC095C Half and Half

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc095/tasks/arc096_a

この問題は全探索を用いて解くことができます。

コード

ABピザを買う枚数を決めると、AピザとBピザを買う枚数を決めることができます。よってABピザを買う枚数について全探索を行えば良いです。計算量はO(N)です。

1
2
3
4
5
A, B, C, X, Y = map(int, input().split())
ans = 10**10
for i in range(10**5+1):
    ans = min(ans, A*max(X-i, 0) + B*max(Y-i, 0) + 2*C*i)
print(ans)

もちろん、O(1)で解くことができます。

1
2
3
4
5
6
7
A,B,C,X,Y = map(int,input().split())
min_xy = min(X,Y)
max_xy = max(X,Y)
ans1 = 2 * C * min_xy + A * (X-min_xy) + B * (Y-min_xy) # 無駄にならない範囲でABピザを買い、残りを買う
ans2 = A*X + B*Y # ABピザを買わない
ans3 = 2 * C * max_xy # ABピザだけを買う
print (min(ans1,ans2,ans3))

記事情報

  • 投稿日：2020年5月11日
  • 最終更新日：2020年5月11日