I will explain ** A, B, C, D problems ** of ** AtCoder Beginner Contest 183 ** as carefully as possible with ** Python 3 **.

I am aiming to explain a solution that satisfies the following three points, not just a method that can be solved.

--Simple: You don't have to think about anything extra --Easy to implement: I'm glad that mistakes and bugs are reduced ――It doesn't take long: The performance goes up and you have more time left for later problems.

If you have any questions or suggestions, please leave a comment or Twitter. Twitter: u2dayo

[ABC183 Summary](# abc183-Summary) [A problem "ReLU"](#a problem relu) [B problem "Billiards"](#b problem billiards) [C problem "Travel"](#c problem travel) [D problem "Water Heater"](#d problem water-heater)

ABC183 Summary

Total number of submissions: 7199

performance

Performance	AC	Score	time	Ranking(Within Rated)
200	AB----	300	32 minutes	5526(5365)Rank
400	ABC---	600	99 minutes	4586(4426)Rank
600	ABC---	600	38 minutes	3791(3632)Rank
800	ABCD--	1000	88 minutes	2963(2807)Rank
1000	ABCD--	1000	46 minutes	2194(2038)Rank
1200	ABCD--	1000	21 minutes	1554(1399)Rank
1400	ABCDE-	1500	70 minutes	1060(911)Rank
1600	ABCDEF	2100	122 minutes	700(557)Rank
1800	ABCDEF	2100	77 minutes	440(315)Rank
2000	ABCDEF	2100	59 minutes	273(164)Rank
2200	ABCDEF	2100	46 minutes	161(78)Rank
2400	ABCDEF	2100	37 minutes	100(35)Rank

Correct answer rate by color

color	Number of people	A	B	C	D	E	F
Ash	2960	99.5 %	69.2 %	35.0 %	12.5 %	1.9 %	0.8 %
tea	1377	99.7 %	91.7 %	87.5 %	57.4 %	5.8 %	2.5 %
Green	1086	99.6 %	96.9 %	97.0 %	90.7 %	26.4 %	7.6 %
water	664	99.8 %	97.4 %	99.5 %	98.6 %	69.7 %	34.5 %
Blue	333	100.0 %	99.7 %	100.0 %	100.0 %	94.6 %	76.0 %
yellow	124	95.2 %	94.3 %	94.3 %	95.2 %	96.0 %	91.9 %
orange	28	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %	96.4 %
Red	9	88.9 %	88.9 %	88.9 %	88.9 %	88.9 %	100.0 %

Display rate, ash does not include first-time participants

Brief commentary

A problem (7152 people AC) "ReLU" Use the

if statement to separate cases.

B problem (5919 AC) "Billiards"

You can see it by considering the ratio of "speed in the $ x $ direction" and "speed in the $ y $ direction".

C problem (4633 AC) "Travel"

Maximum $ (8-1)! = 7! = 5040 $ Try all the street visit orders. In Python, you can easily generate all permutations using `itertools.permutations`.

D problem (3400 people AC) "Water Heater" Using the

cumulative sum (imos method), you can find out how much hot water is used each time by $ O (N) $.

E problem (1393 people AC) "Queen on Grid" [not explained in this article]

Cumulative sum DP.

F problem (789 AC) "Confluence" [not explained in this article] Use

Unionfind and $ N $ Counters. If you add the smaller size Counter to the larger size of the connected component, it will be in time.

Results of me (Unidayo) (reference)

screenshot.381.png

It was a blue coder ** for only ** 23 hours.

A problem "ReLU"

** Problem page **: A --ReLU ** Gray Coder Correct Answer Rate **: 99.5% ** Brown Coder Correct Answer Rate **: 99.7% ** Green Coder Correct Answer Rate **: 99.6%

The ReLu function is a function often used as a transfer function for deep learning.

code

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

B problem "Billiards"

** Problem page **: B --Billiards ** Gray Coder Correct Answer Rate **: 69.2% ** Brown Coder Correct Answer Rate **: 91.7% ** Green Coder Correct Answer Rate **: 96.9%

Consideration

$ G_x --S_x = T_x $, $ S_y + G_y = T_y $. From the Official Explanation Figure, you can think of the triangle below.

The following relationship holds based on the similarity / ratio of triangles.

Δx = \frac{S_y}{T_y}・ T_x

The answer is $ S_x + Δx $ because $ Δx $ is the length from $ S_x $ to the reflection point on the wall. Note that $ T_x $ and $ Δx $ are negative when the target is on the left side (minus direction of the $ x $ axis). Therefore, there is no need to separate cases.

code

sx, sy, gx, gy = map(int, input().split())

tx = gx - sx
ty = sy + gy
dx = tx * sy / ty
print(sx + dx)

C problem "Travel"

** Problem page **: C --Travel ** Gray Coder Correct Answer Rate **: 35.0% ** Brown Coder Correct Answer Rate **: 87.5% ** Green Coder Correct Answer Rate **: 97.0%

Consideration

** * It is easier to understand if it matches the subscript of the array, so we will start from the city $ 0 $. ** **

The city $ 0 $ at the beginning and the city $ 0 $ at the end are fixed no matter what order you visit the city.

There are a total of $ (N-1)! $ Ways to visit the city from $ 1 $ to $ N -1 $. The maximum is $ N = 8 $, so there are only $ 7! = 5040 $.

** Therefore, it's enough to try all the visit orders and count the number of things that are just $ K $. ** **

Implementation

If you want to generate all possible permutations in Python, you can use the permutations of the itertools module.

For this issue, I want to create all the permutations that can be made by rearranging (1, 2, 3, ..., N -1). To do this, pass range (1, N) as an argument to permutations.

Specifically, you can write as follows.

for per in permutations(range(1, N)):
    #processing

code

from itertools import permutations

N, K = map(int, input().split())
T = []

for _ in range(N):
    s = list(map(int, input().split()))
    T.append(s)

ans = 0

for per in permutations(range(1, N)):
    score = 0  #It is the time taken in the order of this visit
    prev = 0  #First start from city 0
    for i in range(N - 1):
        cur = per[i]
        score += T[prev][cur]  #Head from city prev to city cur
        prev = cur
    score += T[prev][0]  #Finally go to city 0

    if score == K:
        #If you can go around with just K, the answer+1
        ans += 1

print(ans)

D problem "Water Heater"

** Problem page **: D --Water Heater ** Gray Coder Correct Answer Rate **: 12.5% ** Brown Coder Correct Answer Rate **: 57.4% ** Green Coder Correct Answer Rate **: 90.7%

Consideration

Times are separated by integers and have a maximum of $ 200,000 $. Therefore, consider creating an array that records the amount of hot water consumed each hour. Of course, adding $ P_i $ to every section of $ N $ people is not enough.

Therefore, we use the cumulative sum. ** "Add $ P_i $ from $ S_i $ to $ T_i --1 $" ** can be paraphrased in this way.

-** "$ + P_i $ from $ S_i $ to the end of the array" ** -** "$ -P_i $ from $ T_i $ to the end of the array" **

If you only do the first operation with the usual cumulative sum, $ P_i $ will be added after $ T_i $. Therefore, if you subtract $ P_i $ from after $ T_i $ to cancel it, you can add to the interval by the cumulative sum.

Do these $ 2 $ operations on the array by $ 1 $ people each. Finally, find the cumulative sum to see if your hot water consumption is less than $ W $ at all times. To do this, you can use the max function to determine if the maximum cumulative sum is less than or equal to $ W $.

The ** "algorithm that adds intervals using the cumulative sum" ** used in this problem is sometimes called the ** imos method ** from the name of the developer. When working on a one-dimensional array, it's a simple algorithm that just does the cumulative sum operation $ 2 $ times.

code

From @ c-yan's comment, it has been improved to use the max function for the final judgment. Thank you!

from itertools import accumulate

C = 200005  #The length C of the cumulative sum array. Set the number appropriately larger than 200,000.

N, W = map(int, input().split())
seq_a = [0] * C

for _ in range(N):
    s, t, p = map(int, input().split())
    seq_a[s] += p
    seq_a[t] -= p

S = list(accumulate(seq_a))

if max(S) <= W:
    print('Yes')
else:
    print('No')

[AtCoder explanation] Control the A, B, C, D problems of ABC183 with Python!

table of contents

ABC183 Summary

performance

Correct answer rate by color

Brief commentary

Results of me (Unidayo) (reference)

A problem "ReLU"

code

B problem "Billiards"

Consideration

code

C problem "Travel"

Consideration

Implementation

code

D problem "Water Heater"

Consideration

code