[PYTHON] AtCoder Beginner Contest 108 Review of past questions

Time required

Impressions

I wasn't able to devote myself to writing an article over 10,000 characters about itertools. Also, when I was solving this, I was stuck in a mystery at B and I ran out of time, so I could not spend enough time on D. Impossible! When I looked at the answer, it was the expected solution, so I need to think carefully ... This lack of stability is the reason why it stays green, but how can it be improved?

Problem A

The odd number is calculated by k // 2, so the rest is an even number.

answerA.py

k=int(input())
print((k-k//2)*(k//2))

B problem

This issue alone took over 30 minutes. For some reason, I misunderstood that one side of the square was parallel to x and y ... After all, we can draw a congruent triangle as follows, so we can linearly derive the coordinates of the remaining squares from the coordinates of the given two points.

answerB.py

x1,y1,x2,y2=map(int,input().split())
a=x1-x2
b=y1-y2
print(x2+b,y2-a,x1+b,y1-a)

C problem

Since $ a + b, b + c, c + a $ is a multiple of K, consider the remainder of $ a, b, c $ divided by K.

Here, if each remainder is $ x, y, z (0 \ leqq x, y, z \ leqq K) $, then $ x + y = (0 \ or \ K), y + z = (0) It suffices if \ or \ K), z + x = (0 \ or \ K) $ holds, and $ (x, y, z) = (\ frac {K} {2}, It will be \ frac {K} {2}, \ frac {K} {2}) \ or \ (0,0,0) $.

Also, I quickly found out that I needed a remainder, so I saved all the remainders in the dictionary, but I only need to save them for k // 2 or 0.

answerC.py

n,k=map(int,input().split())
d=dict()
for i in range(k):
    d[i]=0
for i in range(1,n+1):
    d[i%k]+=1
#print(d)
if k%2!=0:
    print(d[0]**3)
else:
    print(d[0]**3+d[k//2]**3)

D problem

** Graph problems are always scary ... **. I want to solve a lot of graph problems and get used to it, but I don't have much time. I couldn't solve it during the contest, so I glanced at this blog, but just follow the policy I made. I realized that I should have done it, and withered. ** I don't have enough power to push it according to my own policy ** ...

Since all the paths are different and all the paths from 0 to L-1 must be generated in 1 increments and there are many restrictions, I first felt that ** it is not good to think about the paths properly **. Also, since there can be two ways depending on whether the path is passed or not, I noticed that ** sides can be expressed by whether or not the bit is set **.

I couldn't ** draw an accurate diagram and experiment ** to see if it could be expressed with this bit. Although it is amakudari, you can change the side to be selected depending on whether the bit is set or not by doing the following.

In the above case, 0 to 15 can be represented as 16 different paths by considering each ** $ i → i + 1 $ as the $ i-1 $ bit ** (L = 16). in the case of). In the same way, you can easily see that 0 to 31 can be represented by adding the vertices of 6 (L = 32). Therefore, if L is a power of 2, it seems that it can be expressed, and in other cases (L = 19).

Here, the more edges you add, the more different paths you will have, so consider increasing the edges, but don't blindly increase them. For example, suppose you add 4 → 5 edges. At this time, the number of different paths increases by $ 2 ^ 3 $ ($ \ because $ 1 → 4 paths are $ 2 ^ 3 $), so the total number of different paths is 24. Therefore, it exceeds 19 lines. Thinking in the same way, ** adding an edge extending from each vertex $ i $ to the largest number of vertices will increase the number of paths that differ by $ 2 ^ {i-1} $ **. In addition, the path that increases at that time can be expressed in increments of 1 (it is not difficult if you draw a diagram and experiment).

Therefore, when L is displayed in binary, determine how many vertices there are from the bit of the highest digit, look at the 1's in order with the bits below it, and if there is 1 of that bit, By extending the edges from the corresponding vertices to the last vertex, it is possible to create L different paths while satisfying the number of vertices and the number of edges.

Also, I think the explanation is a little difficult to understand, so I will show you how to solve it when L = 19 (by handwriting) below.

Furthermore, in the code below, the dropwhile function is used to find the top bit (searching from the top of $ \ because $ to find the element that becomes 1 for the first time). It was alive to study itertools while writing this article.

answerD.py

from itertools import dropwhile
l=int(input())
#Arrange from the upper bit
k=[(l>>i & 1) for i in range(20)][::-1]
#List below 1 bit for the first time
k=list(dropwhile(lambda x:x==0,k))

n=len(k)
path=[]
for i in range(n-1):
    path.append((i+1,i+2,0))
    path.append((i+1,i+2,2**i))

path_len=2**(n-1)
for i in range(1,n):
    if k[i]:
        x=n-1-i
        path.append((x+1,n,path_len))
        path_len+=(2**x)

m=len(path)
print(n,m)
for i in path:
    print(i[0],i[1],i[2])