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

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

table of contents

[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 %

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 ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 99.5% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 99.7% ** <font color = # 008000> Green </ font> 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 ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 69.2% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 91.7% ** <font color = # 008000> Green </ font> 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.

abc183b.png

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 ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 35.0% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 87.5% ** <font color = # 008000> Green </ font> 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 ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 12.5% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 57.4% ** <font color = # 008000> Green </ font> 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')



Recommended Posts