** 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
ABC187 Summary Problem A "Large Digits" B problem "Gentle Pairs" C problem "1-SAT"
Total number of submissions: 7239
| 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 |
| 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 % |
** 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.
Receives as a string, looks at $ A and B $ digit by $ 1 $, and converts them to integers. Finally, you can output the larger one.
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))
** 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%
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) $.
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) **
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)
** 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%
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".
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.
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