AtCoderBeginnerContest183 Review & Summary

AtCoder ABC183 This is a summary of the AtCoder Beginner Contest 183 problems that took place on 2020-11-15 (Sun), starting with problem A and taking into account the considerations. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary

Problem A ReLU

Problem statement The ReLU function is defined as follows. Given the integer $ x $, find $ ReLU (x) $.

ReLU function familiar with activation function.

`abc183a.py`


x = int(input())
if x >= 0:
    print(x)
else:
    print(0)

Problem B Billiards

Problem statement Takahashi is playing billiards on the $ 2 $ dimensional plane. The $ x $ axis is a wall, and when you hit the sphere, the sphere bounces so that the angle of incidence and the angle of reflection are equal. Now Takahashi's ball is in $ (S_x, S_y) $. When you hit a sphere at a certain coordinate, the sphere rolls linearly toward that coordinate. After reflecting the sphere exactly $ 1 $ on the $ x $ axis, where should we aim on the $ x $ axis to pass $ (G_x, G_y) $?

Since the constraint was $ 0 <S_y, G_y \ leq 10 ^ 6 $, we set $ G_y $ as negative and solved it as the intersection of the equation of a line and the $ x $ axis.

x = S_x - S_y × (G_x - S_x) ÷ (G_y - S_y)

`abc183b.py`


s_x, s_y, g_x, g_y = map(int, input().split())
g_y = -g_y
print(s_x - s_y * (g_x - s_x) / (g_y - s_y))

C problem Travel

Problem statement There are $ N $ cities. It takes $ T_ {i, j} $ to move from city $ i $ to city $ j $. How many routes depart from city $ 1 $, visit all cities at just $ 1 $ degrees, and then return to city $ 1 $, with a total travel time of just $ K $? ??

Since the constraint is as small as $ 2 \ leq N \ leq 8 $, I was able to solve it within the execution time limit even if I searched all, but when I first saw the problem, $ 1 \ to 2 \ to 3 \ to 4 \ to The 1 $ route and the $ 1 \ to 4 \ to 3 \ to 2 \ to 1 $ route have the same total travel time due to the constraint of $ T_ {i, j} = T_ {j, i} $. , I was thinking that I could reduce the amount of calculation if I used a recursive function or something, so it took me a long time to start solving.

`abc183c.py`


import itertools
import numpy as np
n, k = map(int, input().split())
matrix = np.zeros((n, n), dtype=int) 
for i in range(n):
    x_list = list(map(int, input().split()))
    for j in range(n):
        matrix[i, j] = x_list[j]
no_list = range(1, n)
count = 0
for temp_list in itertools.permutations(no_list):
    no = 0
    total = 0
    for next_no in temp_list:
        total += matrix[no, next_no]
        no = next_no
    total += matrix[no, 0]
    if total == k:
        count += 1
print(count)

D problem Water Heater

Problem statement There is a $ 1 $ water heater that can supply $ W $ liters of hot water per minute. There are $ N $ people. The $ i $ th person plans to use $ P_i $ liters of water boiled in this water heater every minute between time $ S_i $ and $ T_i $ (excluding time $ T_i $). The hot water cools quickly and cannot be stored. Is it possible to supply hot water to everyone as planned?

For some reason, I solved it with dict during the contest, but I can solve it with list as well. In the first place, it is wasteful and regrettable because it is not necessary to manage separately by increasing and decreasing.

`abc183d.py`


n, w = map(int, input().split())
start_dict = {}
end_dict = {}
for i in range(n):
    s, t, p = map(int, input().split())
    if s in start_dict:
        start_dict[s] += p
    else:
        start_dict[s] = p
    if t in end_dict:
        end_dict[t] += p
    else:
        end_dict[t] = p
now = 0
flag = 1
for i in range(2 * 100000):
    if i in start_dict:
        now += start_dict[i]
    if i in end_dict:
        now -= end_dict[i]
    if now > w:
        flag = 0
        break
if flag == 1:
    print("Yes")
else:
    print("No")

Code modified with reference to the explanation.

`abc183d.py`


n, w = map(int, input().split())
a_list = [0] * 200001
for i in range(n):
    s, t, p = map(int, input().split())
    a_list[s] += p
    a_list[t] -= p
for i in range(1, 200001):
    a_list[i] += a_list[i - 1]
if max(a_list) > w:
    print("No")
else:
    print("Yes")

The E problem ended without getting out of'TLE'. I would like to add it when I have time.

Thank you for reading until the end.