[PYTHON] AtCoder Beginner Contest 048 Review of past questions

Time required

Impressions

I took first place for the first time in Bacha! ,Banzai! I want to make an effort to fit it so well. D was a moment when I applied the basic solution to the game problem. (There was a case where I forgot to think about it while saying that. I regret it.)

Problem A

Just take the first letter in order.

answerA.py

x=input().split()
print(x[0][0]+x[1][0]+x[2][0])

B problem

Considering the smallest multiple of x above a (ceil function) and the largest multiple of x below b (floor function), it is only necessary to count the number of multiples of x between the two numbers (including both ends). You can see that. To avoid errors, I used the // operator this time without using the ceil and floor functions.

answerB.py

a,b,x=map(int,input().split())
A=-((-a)//x)
B=b//x
print(B-A+1)

C problem

It is sufficient if $ a_i + a_ {i + 1} <= x $ holds for i = 1 to n-1. Here, in order to minimize the number of operations, ** consider all the sums of two adjacent numbers **, so ** do it greedily from the front ** (I think there are many similar problems with AtCoder). .). Specifically, if $ a_1 $ is less than or equal to x, make $ a_ {i + 1} $ smaller so that $ a_i + a_ {i + 1} <= x $ holds from i = 1 to n-1. To do. If it already holds, do nothing. Here, either $ a_i $ or $ a_ {i + 1} $ should be made smaller, but if $ a_ {i + 1} $ is made smaller, $ a_ {i + 1} + a_ {i + 2 You can expect $ a_j + a_ {j + 1} $ to be smaller in j> i as} $ will be smaller. Therefore, from this, it can be said that the minimum number of operations can be achieved by greedily doing it from the front.

answerC.py

n,x=map(int,input().split())
a=list(map(int,input().split()))
if a[0]>x:
    ans=a[0]-x
    a[0]=x
else:
    ans=0
for i in range(1,n):
    if a[i-1]+a[i]>x:
        ans+=(a[i-1]+a[i]-x)
        a[i]=x-a[i-1]
print(ans)

D problem

It's a problem of playing a game with two people. There are two main basic policies for such issues. The first is ** pay attention to the final phase of the game **. In competitive programming, it is often not possible to simulate everything, so it is often good to focus on the final phase. The second is ** what the phase of the game is **. Games that are solved by competitive programming are devised to solve, and many of them can be divided into several states. (In this problem, the operations are alternated, so ** even ** is also an important checkpoint.)

The solution is as follows while considering the above two points. First, in the final phase, you can see that either (1) you cannot remove it because there are only two characters left (because it is at both ends), or (2) you cannot remove it because the same characters are next to each other. In addition, it is important that the characters at both ends ** can never be removed **. In other words, the remaining two characters in pattern (1) are two characters at both ends, and the same characters adjacent to each other in pattern (2) are two characters at both ends (three characters in total). Here, I thought that the last thing left was two or three letters, but a pattern like abababa where two kinds of letters alternate is not so. I didn't notice until I saw the answer ... The consideration is sweet. (Since the case is divided by even and odd, it did not affect the result.) In any case, the number of characters remaining in pattern (1) is ** even ** and the number of characters remaining in pattern (2) is ** odd **, so if n is even in pattern (1), the first player loses and n. When is odd, the second attack is lost, when n is even in the pattern (2), the second attack is lost, and when n is odd, the first attack is lost. (For details, refer to Answer.)

answerD.py

s=input()
n=len(s)
if s[0]==s[-1]:
    if n%2==0:
        print("First")
    else:
        print("Second")
elif s[0]!=s[-1]:
    if n%2==1:
        print("First")
    else:
        print("Second")