[PYTHON] AtCoder Beginner Contest 059 Review of past questions

Past questions solved for the first time

Time required

Problem A

Upper function to capitalize

answerA.py

s1,s2,s3=input().split()
s=s1[0]+s2[0]+s3[0]
print(s.upper())

B problem

Just compare

answerB.py

a=int(input())
b=int(input())
if a>b:
    print("GREATER")
elif a<b:
    print("LESS")
else:
    print("EQUAL")

C problem

It is best to do this ** problem that holds for any i and depends on i + 1 or later ** from the beginning (is it true? I can show it by reductio ad absurdum). The sign may be different for each term, either the odd term is positive and the even term is negative, or the odd term is negative and the even term is positive. Furthermore, when considering each of these two patterns, if each term does not satisfy the pattern, it is necessary to use different codes, and the minimum number of times required to change the term is set to -1 or 1. You can see that it can be achieved. Also, at this time, it is easy to show that it is not necessary to change to -2 or 2, etc. if you think about the case of such a change (I will omit it here, but please comment if necessary) To do.). Once you know this, you can find the answer by thinking in order from the previous section. (Since we consider the sum, we have calculated the cumulative sum first.)

answerC.py

import copy
n=int(input())
a1=[int(i) for i in input().split()]
a2=copy.deepcopy(a1)
#Seeking cumulative sum
for i in range(1,n):
    a1[i]+=a1[i-1]
for i in range(1,n):
    a2[i]+=a2[i-1]

#pm at that point+Or-Record how much you are doing and c is recording the number of times
#The even-numbered term is positive for 1 and the odd-numbered term is positive for 2.(0 origin)
pm1,c1=0,0
pm2,c2=0,0

for i in range(n):
    a1[i]+=pm1
    if i%2==1:
        if a1[i]>=0:
            pm1-=(a1[i]+1)
            c1+=(a1[i]+1)
    else:
        if a1[i]<=0:
            pm1+=(-a1[i]+1)
            c1+=(-a1[i]+1)

for i in range(n):
    a2[i]+=pm2
    if i%2==0:
        if a2[i]>=0:
            pm2-=(a2[i]+1)
            c2+=(a2[i]+1)
    else:
        if a2[i]<=0:
            pm2+=(-a2[i]+1)
            c2+=(-a2[i]+1)

print(min(c1,c2))

D problem

I want to be able to solve this kind of problem, which is insanely frustrating. First, we needed to keep in mind that these ** game problems are often easier when you think about what the final form will be **. However, I thought of the case of misreading the problem statement and ** acting optimally ** as always maximizing it (the code of answerD_wrong.py), but this is not optimal at all. did. At this point, I came up with the idea that the two mountains should be as close as possible, but I wasn't sure because I was actually trying to simulate them. However, if you dig as close as possible, it's easy to see that there are people who can't even try to get closer. In other words, if the difference between the two mountains is 1 or less, you have to make it ** 2 or more from the condition that ** i is 1 or more (two stones from one to the other mountain). Even if you add one, the difference between the stones will change by 3.) Conversely, the other person receives the difference between the two mountains when the difference is 2 or more, so by adjusting it appropriately, you can pass it when the difference between the two mountains is 1 or less. In other words, you can see that the composition of ** people with a difference between two mountains of 1 or less ** and ** people with a difference between two mountains of 2 or more ** will not collapse in any way. Therefore, it is only necessary to consider what the difference between the two mountains will be in the initial state. This hypothesis can also be supported by ** the final form of loss . This is because the final form of loss is (0,0), (0,1), (1,0), (1,1), so the difference between the two peaks is less than or equal to 1. In other words, the person who receives the difference between the two mountains is 2 or more, by making the difference between the two mountains 1 or less ( optimal ), the opponent's mountain will definitely be lost in the end. You can see that you can go. From the above consideration, if the difference between the two mountains is 2 or more in the initial state, Alice wins, and if it is 1 or less, Brown wins. ( Experiment is important! **)

answerD_right.py

x,y=map(int,input().split())
print("Alice" if abs(x-y)>1 else "Brown")

answerD_wrong.py

def next_tup(x,y):
    if x==0 or x==1:#Always increase x
        x,y=y,x
    k=x//2
    x-=2*k
    y+=k
    return (x,y)

def defeat(tup):
    return tup==(1,1) or tup==(0,1) or tup==(1,0) or tup==(0,0)

X,Y=map(int,input().split())
if defeat((X,Y)):
    print("Brown")
else:
    ans=[]
    x_sub1,y_sub1=X,Y
    f1=0
    while True:
        z=next_tup(x_sub1,y_sub1)
        if defeat(z):
            break
        else:
            x_sub1,y_sub1=z
            if f1==0:
                f1=1
            else:
                f1=0
    ans.append(f1)
    x_sub2,y_sub2=Y,X
    f2=0
    while True:
        z=next_tup(x_sub2,y_sub2)
        if defeat(z):
            break
        else:
            x_sub2,y_sub2=z
            if f2==0:
                f2=1
            else:
                f2=0
    ans.append(f2)
    if 0 in ans:
        print("Alice")
    else:
        print("Brown")