AtCoder Beginner Contest 059 Review of past questions

Past questions solved for the first time

Time required

スクリーンショット 2020-01-08 8.31.20.png

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")

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 105 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 103 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 092 Review of past questions
AtCoder Beginner Contest 099 Review of past questions
AtCoder Beginner Contest 065 Review of past questions
AtCoder Beginner Contest 053 Review of past questions
AtCoder Beginner Contest 094 Review of past questions
AtCoder Beginner Contest 063 Review of past questions
AtCoder Beginner Contest 107 Review of past questions
AtCoder Beginner Contest 071 Review of past questions
AtCoder Beginner Contest 064 Review of past questions
AtCoder Beginner Contest 082 Review of past questions
AtCoder Beginner Contest 084 Review of past questions
AtCoder Beginner Contest 068 Review of past questions
AtCoder Beginner Contest 058 Review of past questions
AtCoder Beginner Contest 043 Review of past questions
AtCoder Beginner Contest 098 Review of past questions
AtCoder Beginner Contest 114 Review of past questions
AtCoder Beginner Contest 045 Review of past questions
AtCoder Beginner Contest 120 Review of past questions
AtCoder Beginner Contest 108 Review of past questions
AtCoder Beginner Contest 106 Review of past questions