Codejam2022 Round 1B: Pancake Deque
5241 ワード
問題
美味しさレベルが記載されたパンケーキをDequeの両端から提供する。レベルが以前に提供されたものと同等以上の時のみ代金を支払う場合、代金を支払う顧客の数が最大になる順番で提供したとすると、何人の顧客が支払いをすることになるかを求める。
アルゴリズム
Dequeの両端で、小さいレベルから提供していく。両端で比較して、レベルが小さい方のパンケーキが、これまでの最大より小さいレベルの時にはフリーで提供されることになるが、最大レベルと同等以上であれば、小さい方を先に提供した方がベター。そうしなければ、先に大きい方のパンケーキが提供されて、最大が更新されることで、小さい方のパンケーキがフリーで提供されることになるため。
実装
入力はリストとして保持し、二つのポインタで両端位置を表す。両端の値の比較、最小の値の方のポインタ移動、支払い対象の顧客数のカウントと最大値の更新を
T = int(input())
for t in range(1, T + 1):
N = int(input())
ps = list(map(int, input().split()))
left, right = 0, N - 1
ret = 0
prev_max = None
while left <= right:
curr = min(ps[left], ps[right])
if ps[left] >= ps[right]:
right -= 1
else:
left += 1
if prev_max is None or prev_max <= curr:
ret += 1
prev_max = max(curr, prev_max) if prev_max is not None else curr
print('Case #{}: {}'.format(t, ret))
この問題は比較的容易な部類だった模様。全体の約８０パーセントの参加者が3つのテストセットをパスしていた。
Author And Source
この問題について(Codejam2022 Round 1B: Pancake Deque), 我々は、より多くの情報をここで見つけました https://zenn.dev/satojkovic/articles/f926ea91b3bd73著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol