Atcoder AGC020 B - Ice Rink Game 別解集

このゲーム スケートリンクでやる必要あった？

累積和的なヤツ？

後ろ側から順番に見ていき、highとlowを更新していく
今の順番の数字がその時点のhighより大きい、lowより小さい、またはその中間かで対応が違う
lowは毎回更新されるが、highはそうとも限らないのが引っ掛かったポイント

math.py

K=int(input())
A=list(map(int,input().split()))

if A[-1]!=2:
    print(-1)
    exit()

low=2
high=3
for item in A[::-1]:
    #print(low,high)
    if high<item:
        print(-1)
        exit()
    elif item<low:
        low=(-((-low)//item))*item
        if low>high:
            print(-1)
            exit()
        high=max(low+item-1,high+item-1-high%item)
    else:
        low=item
        if low>high:
            print(-1)
            exit()
        high=low+item-1
print(low,high)

二分探索

ラウンドが精々10**5くらいなので人数を決め打ちしてシミュレーションしてもlogNくらいなら大丈夫
なのでゲーム開始前の人数を二分探索で探せばよい
実現できないラウンド設定の場合はバグるので最後にhighとlowをシミュレーションにかけて正しい答えになるか確かめようね

最初のころは終了条件とかmiddleの値を2で切り捨てるかどうかで迷ってた
試行錯誤したけど今の書き方が気に入った
にぶたんは初期設定の範囲をばかでかくしてTLE寸前にするとハラハラしてたのしい

bisect.py

K=int(input())
A=list(map(int,input().split()))

def func(num):
    for item in A:
        num=num//item*item
    return num

ok=10**20
ng=0

while ok-ng>1:
    mid=(ok+ng)//2
    if func(mid)>=2:
        ok=mid
    else:
        ng=mid

low=ok

ok=10**20
ng=0

while ok-ng>1:
    mid=(ok+ng)//2
    if func(mid)>=4:
        ok=mid
    else:
        ng=mid

high=ng

if func(low)==2 and func(high)==2:
    print(low,high)
else:
    print(-1)