AtCoder Beginner Contest 108 Review of past questions

Time required

スクリーンショット 2020-05-09 10.27.05.png

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.

スクリーンショット 2020-05-09 10.27.05.png

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.

IMG_0331.JPG

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.

IMG_0332.PNG

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

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 083 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 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 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
AtCoder Beginner Contest 122 Review of past questions
AtCoder Beginner Contest 125 Review of past questions
AtCoder Beginner Contest 109 Review of past questions
AtCoder Beginner Contest 118 Review of past questions
AtCoder Beginner Contest 080 Review of past questions