Codejam2022 Round 1B: Pancake Deque

問題

美味しさレベルが記載されたパンケーキをDequeの両端から提供する。レベルが以前に提供されたものと同等以上の時のみ代金を支払う場合、代金を支払う顧客の数が最大になる順番で提供したとすると、何人の顧客が支払いをすることになるかを求める。

https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b/0000000000acd59d

アルゴリズム

Dequeの両端で、小さいレベルから提供していく。両端で比較して、レベルが小さい方のパンケーキが、これまでの最大より小さいレベルの時にはフリーで提供されることになるが、最大レベルと同等以上であれば、小さい方を先に提供した方がベター。そうしなければ、先に大きい方のパンケーキが提供されて、最大が更新されることで、小さい方のパンケーキがフリーで提供されることになるため。

実装

入力はリストとして保持し、二つのポインタで両端位置を表す。両端の値の比較、最小の値の方のポインタ移動、支払い対象の顧客数のカウントと最大値の更新を$\rm{left} \leq \rm{right}$の間繰り返す。

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つのテストセットをパスしていた。