I would like to review yesterday's Keyence2020.

This time's results

Impressions

I couldn't solve it at all in the previous dwango (I haven't reviewed it, so I have to review it soon), but this time I was scared. The reason I couldn't solve the fourth question for more than an hour was ** I didn't have enough logic and spirit **, and although it was a good question that I could do if I thought about it carefully, I couldn't do it ** during the contest. I was ... I haven't seen any mental growth since I took the university entrance exam, so I would like to grow that part as well.

Problem A

It is possible to continue to select the larger h and w, so do so (is it too easy?). Not h, w, n = map (int, input (). Split ()), huh? It became.

`answerA.py`


import math
h=int(input())
w=int(input())
n=int(input())
k=max(h,w)
print(math.ceil(n/k))

Problem B

The moment I saw it, I knew it was interval scheduling. Use interval scheduling to take the maximum number of intervals so that there are no intersections when taking intervals with common parts. In interval scheduling, the algorithm sorts in ascending order by the end time of the interval, and the interval whose start time is after the end time is taken in order from before (sorted). Mathematical induction can prove why the maximum number of intervals can be taken by interval scheduling. Assuming that there was an optimal section selection method, this optimal selection method shows this because the end time is not late (✳︎) when the same number is selected compared to any other selection method (simplified proof). To do.). When n = 1, the one with the earliest end time is selected. When n = k holds, n = k + 1 selects the section that starts after the end time of the section selected by n = k and has the earliest end time, so even n = k + 1 It holds in the same way. Therefore, it can be said that (✳︎) holds in the algorithm based on interval scheduling. When the above is implemented, it becomes as follows. It can be easily solved by thinking that x-l is the start time and x + l is the end time.

`answerB.py`


n=int(input())
sec=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    sec[i][0]+=l
    sec[i][1]-=l
sec.sort()

ans=0
#-inf
t=-10000000000
for i in range(n):
    #=Don't forget to put on
    if t<=sec[i][1]:#The start must be greater than or equal to some maximum coordinates of the robot arm
        ans+=1#If above+1
        t=sec[i][0]#Updated maximum coordinates with robot arm
print(ans)

C problem

It was surprisingly easy when I thought it was a construction. What this. I thought there was k> n and I got stuck in a corner case of 10 ** 9 and issued 4WA. I'm sorry. 1 <= l <= r <= n, but when you think about the case of l = r, it ends immediately (at first 1,1,1,1,…, r-1,…, r) It took a long time because I was thinking about -1, r + 1, ..., r + 1. ** Simplifying the problem is important in construction ** ??). Considering a pattern in which s is k and s + 1 is n-k, k can be selected with l = r. However, when $ s = 10 ^ 9 $, s + 1 goes out of the constraint, so you can set it to 1 instead of s + 1 (because the sum of 1 does not become s).

`answerC.py`


n,k,s=map(int,input().split())
if s<10**9:
    x=[s]*k
    y=[s+1]*(n-k)
else:
    x=[s]*k
    y=[1]*(n-k)
z=" ".join(map(str,x))+" "+" ".join(map(str,y))
print(z)

D problem

I'm always frustrated because I can't solve this level of problem. However, I think I've grown up because I've been doing some tricks recently with a slightly twisting problem like the C problem. When I saw the stronger tweet after the contest, I noticed that it was $ 2 ^ {18} $, so it was about $ 10 ^ 5 $, and I could see that I could do a full search. First, decide the front and back of each card, and if you decide, you can see the number that you can see in the final state of each card, so in that state you sort in ascending order with bubble sort and think about how many times you swapped at that time , You can find the minimum number of swaps. It is also important to note that the front cards can only be placed an even number of distances, and the back cards can only be placed an odd number of distances.

I was able to make a policy, but I didn't consider the case where there are multiple same numbers, so I can't do anything with WA. I would like to give it as soon as AC is possible.

[PYTHON] Keyence Programming Contest 2020 Review