ARC050B 花束

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

二分探索

はじめに

カテゴリーAtCoder版蟻本中級編では、AtCoder 版!蟻本 (中級編)でまとめられている問題をPythonで解いています。

問題

https://atcoder.jp/contests/arc050/tasks/arc050_b

方針

二分探索を用いて解くことができます。

ABC023D 射撃王でも紹介させていただいたmeguru_bisectを使うと、二分探索をバグりにくく実装できます。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
R, B = map(int,input().split())
x, y = map(int,input().split())
def is_ok(K):
if K>R or K>B:
return False
if (R-K)//(x-1) + (B-K)//(y-1) >= K:
return True
return False

def meguru_bisect(ng, ok):
while (abs(ok - ng) > 1):
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
return ok
print (meguru_bisect(10**19,0))

記事情報

  • 投稿日:2020年6月24日
  • 最終更新日:2020年6月24日