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

** A, B, C problems ** of ** AtCoder Beginner Contest 187 ** will be explained as carefully as possible with ** Python3 **.

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

ABC187 Summary Problem A "Large Digits" B problem "Gentle Pairs" C problem "1-SAT"

ABC187 Summary

Total number of submissions: 7239

performance

Performance AC Score time Ranking(Within Rated)
200 AB---- 300 32 minutes 5684(5487)Rank
400 ABC--- 600 79 minutes 4770(4575)Rank
600 ABC--- 600 28 minutes 3971(3777)Rank
800 ABCD-- 1000 104 minutes 3110(2920)Rank
1000 ABCD-- 1000 55 minutes 2306(2116)Rank
1200 ABCD-- 1000 31 minutes 1643(1454)Rank
1400 ABCDE- 1500 105 minutes 1136(953)Rank
1600 ABCDE- 1500 64 minutes 770(593)Rank
1800 ABCDE- 1500 39 minutes 511(345)Rank
2000 ABCDEF 2100 90 minutes 320(184)Rank
2200 ABCDEF 2100 61 minutes 191(90)Rank
2400 ABCDEF 2100 46 minutes 103(41)Rank

Correct answer rate by color

color Number of people A B C D E F
Ash 2780 97.9 % 75.2 % 46.7 % 15.9 % 1.5 % 0.1 %
tea 1298 98.8 % 97.5 % 90.3 % 56.3 % 5.7 % 0.8 %
Green 1051 99.6 % 99.2 % 97.9 % 79.5 % 19.1 % 2.0 %
water 666 99.7 % 99.5 % 99.4 % 92.5 % 59.5 % 10.2 %
Blue 344 99.7 % 99.7 % 99.7 % 99.1 % 88.7 % 45.9 %
yellow 160 97.5 % 96.2 % 96.2 % 94.4 % 93.8 % 79.4 %
orange 30 93.3 % 93.3 % 96.7 % 100.0 % 96.7 % 86.7 %
Red 9 77.8 % 77.8 % 77.8 % 77.8 % 66.7 % 100.0 %

Brief commentary

A problem (7110 people AC) "Large Digits"
$ 1 $ Add digits at a time and output the larger one.
B problem (6187 people AC) "Gentle Pairs"
Full search with double for loop.
C problem (5025 people AC) "1-SAT"
If there is a "dissatisfied string", it can only be one of the given $ N $ strings. If you use the `set` type, you can determine whether it exists with $ O (1) $, so you can solve it with $ O (N) $ as a whole.
D problem (3316 people AC) "Choose Me" [not explained in this article]
It is best to give a speech in descending order of
$ 2A + B $. Therefore, if you sort in descending order of $ 2A + B $ and make a speech until the Takahashi faction is larger than the Aoki faction, you can solve it with $ O (NlogN) $.
E problem (1250 people AC) "Through Path" [not explained in this article]
Take root appropriately. (Apex $ 1 $ is fine) Next, do a breadth-first search to find the height of each vertex. Then, each query can be regarded as "$ + x $ for a child of a vertex" or "$ + x $ for the whole and $ -x $ for a child of a vertex" using the calculated height. .. Finally, you can do a breadth-first search from the root again and find the answer with $ O (N + Q) $.
F problem (438 people AC) "Close Group" [not explained in this article]
If you write the code that transitions from each subset with
bitDP, you can solve it with $ O (3 ^ N) $.

Problem A "Large Digits"

** Problem page **: A --Large Digits ** <font color = # 808080> Gray Coder Correct Answer Rate **: 97.9% ** <font color = # 804000> Brown Coder Correct Answer Rate **: 98.8% ** <font color = # 008000> Green Coder Correct Answer Rate **: 99.6%

It is a very troublesome problem for A problem.

Implementation

Receives as a string, looks at $ A and B $ digit by $ 1 $, and converts them to integers. Finally, you can output the larger one.

code

A, B = input().split()
a, b = 0, 0

for x, y in zip(A, B):
    a += int(x)
    b += int(y)

print(max(a, b))

B problem "Gentle Pairs"

** Problem page **: B --Gentle Pairs ** <font color = # 808080> Gray Coder Correct Answer Rate **: 75.2% ** <font color = # 804000> Brown Coder Correct Answer Rate **: 97.5% ** <font color = # 008000> Green Coder Correct Answer Rate **: 99.2%

Consideration

Given the coordinates of a $ 2 $ point, the slope is

$ \ frac {y coordinate difference} {x coordinate difference} $

Is required at.

Since the maximum number of points $ N $ is $ 10 ^ 3 = 1000 $, there are only $ 2 $ point pairs at most $ \ frac {1000 \ times {(1000-1)}} {2} = 499500 $ pairs. .. You can solve it by checking if the slope $ t $ is $ -1 \ le {t} \ le {1} $ for all combinations.

The amount of calculation is $ O (N ^ 2) $.

Implementation

Let the $ x $ coordinate difference be $ dx $ and the $ y $ coordinate difference be $ dy $. The slope $ t $ is $ \ frac {dy} {dx} $.

** If $ dx $ becomes $ 0 $, a $ 0 $ division will result in an error, but the constraint of this problem does not give points with the same $ x $ coordinates, so $ dx $ cannot be $ 0 $. .. (You should always be aware of it) **

code

N = int(input())
P = []

for _ in range(N):
    x, y = map(int, input().split())
    P.append((x, y))

ans = 0

for i in range(N):
    x1, y1 = P[i]
    for j in range(i + 1, N):
        x2, y2 = P[j]
        dx = x2 - x1
        dy = y2 - y1
        if -dx <= dy <= dx:
            ans += 1

print(ans)

C problem "1-SAT"

** Problem page **: C-1-SAT ** <font color = # 808080> Gray Coder Correct Answer Rate **: 46.7% ** <font color = # 804000> Brown Coder Correct Answer Rate **: 90.3% ** <font color = # 008000> Green Coder Correct Answer Rate **: 97.9%

Consideration

The $ N $ string $ S $ is ** "a non-empty string of lowercase letters with'!' Added $ 0 $ or $ 1 $ characters "**.

Consider the string $ T $. If $ T $ is not the same as any of $ S $, then it is not a "frustrated string". ** So, if there is a "dissatisfied string", it will be one of the given $ N $ strings $ S $. ** **

The string itself that exists in ** $ S $ will match itself unless you add '!', So it is a "dissatisfied string" as it is. ** There is a chance to add a $ 1 $ character to the beginning of the string, so let's add it. If this doesn't work, it's a "dissatisfied string". If not, it's not a "dissatisfied string".

Implementation

To check "whether a string exists in a set", basically you can write the following code.

if "!" + T in S:
    return T

** Now, be careful about the type of S. ** **

If implemented without thinking, I think S would be a list[]. However, using in on a list is as computationally expensive as the number of elements in the list. This is because a linear search is performed on all the elements of the list to see if even one matches. Therefore, the total amount of calculation is $ O (N ^ 2) $. The maximum $ N = 200,000 $ constraint is not enough.

To reduce the amount of calculation, S is of type set. Confirmation of existence for set type T in S can be made efficient with the complexity of $ O (1) $. This is because the set type is a data structure called hash table.

The total complexity is $ O (N) $, so I was able to solve this problem.

code

N = int(input())

S = set()  #Existence confirmation O(1)I want to do it with, so I will make it a set type

for _ in range(N):
    T = input()
    S.add(T)  #It is add, not append, that is added to set


def solve():
    for T in S:
        if "!" + T in S:
        #T is a dissatisfied string
            return T

    #It's satisfiable because there are no dissatisfied strings (I'm glad to point out typo / spelling mistakes using the IDE)
    return "satisfiable"


print(solve())

Recommended Posts