ABC95 C - Half and Half から学んだ

14448 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク



考えても良くわからず、以下のページの冒頭、"AB ピザの全探索" が見えてピンときた。

ろくに読まずに、思いついたまま書いたら通った。

halfandhalf.py
A,B,C,X,Y = map(int,input().split())

#X,Y 多い方 を 2 倍だけ AB ピザを用意できれば、
#worst case を加味して全探索したことがいえる 
N = 2*max(X,Y)
score = 0
ans = float("inf")
for n in range(N+1):
    cur = (n//2)
    if X-cur >= 0 and Y-cur>=0:
        score = n*C+(X-cur)*A+(Y-cur)*B
    elif X-cur < 0 and Y-cur>=0:
        score = n*C+(Y-cur)*B
    elif X-cur >= 0 and Y-cur <0:
        score = n*C+(X-cur)*A
    else:
        score = n*C

    if score < ans:
        ans = score
print(ans)

勿論、以下の記述でも通る。

halfandhalf.py
A,B,C,X,Y = map(int,input().split())

ans = float("inf")
score = 0
#X,Y の最大値はそれぞれ 10**5 。
#その場合 AB ピザは 2 * 10**5 枚、最大で必要となる
#これがイメージ出来れば以下の記述でも対応可能
for i in range(1+2*10**5):
    if i%2 == 0:
        Z = i//2
        if X-Z >= 0 and Y-Z>=0:
            score = A*(X-Z) + B*(y-z) + C*i
        elif X-Z < 0 and Y-Z >= 0:
            score = B*(Y-Z) + C*i
        elif Y-Z < 0 and X-Z >= 0:
            score = A*(X-Z) + C*i
        else:
            score = C*i
    ans = min(ans,score)

print(ans)

再チャレンジしました。
X , Y が負になる場合に注意して AB ピザの全探索を
すれば大丈夫です。

自力で回答に辿り着けました。
ちょっとは実力が付いたみたいで嬉しいです。

abc95c.py
A,B,C,X,Y = map(int,input().split())

ab_cnt = 2*max(X,Y)
#print(ab_cnt)
ans = 10**100
for i in range(ab_cnt+1):
    if X-(i//2) < 0 and Y-(i//2) < 0:
        num = C*i
    elif X-(i//2) < 0 and Y-(i//2) >= 0:
        num = C*i+(Y-(i//2))*B
    elif X-(i//2) >= 0 and Y-(i//2) < 0:
        num = C*i+(X-(i//2))*A
    else:
        num = C*i+(X-(i//2))*A + (Y-(i//2))*B
    ans = min(ans,num)

print(ans)