** AtCoder Beginner Contest 188 ** ** A, B, C problems ** 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 contact ** Comments ** or ** Twitter **! Twitter: u2dayo
ABC188 Summary Problem A "Three-Point Shot" B problem "Orthogonality" C problem "ABC Tournament"
Total number of submissions: 7831
Performance | AC | Score | time | Ranking(Within Rated) |
---|---|---|---|---|
200 | ABC--- | 600 | 100 minutes | 6064(5867)Rank |
400 | ABC--- | 600 | 49 minutes | 5035(4842)Rank |
600 | ABC--- | 600 | 31 minutes | 4164(3972)Rank |
800 | ABC--- | 600 | 18 minutes | 3256(3064)Rank |
1000 | ABCD-- | 1000 | 76 minutes | 2417(2226)Rank |
1200 | ABC-E- | 1100 | 93 minutes | 1725(1536)Rank |
1400 | ABCDE- | 1500 | 80 minutes | 1192(1012)Rank |
1600 | ABCDE- | 1500 | 50 minutes | 799(628)Rank |
1800 | ABCDE- | 1500 | 28 minutes | 521(364)Rank |
2000 | ABCDEF | 2100 | 95 minutes | 306(193)Rank |
2200 | ABCDEF | 2100 | 72 minutes | 175(95)Rank |
2400 | ABCDEF | 2100 | 60 minutes | 106(45)Rank |
color | Number of people | A | B | C | D | E | F |
---|---|---|---|---|---|---|---|
Ash | 3153 | 98.1 % | 94.9 % | 62.5 % | 5.0 % | 2.7 % | 0.3 % |
tea | 1483 | 99.5 % | 99.3 % | 93.6 % | 27.3 % | 9.6 % | 0.8 % |
Green | 1199 | 99.6 % | 99.7 % | 98.5 % | 62.1 % | 34.5 % | 2.3 % |
water | 680 | 99.6 % | 99.6 % | 98.8 % | 88.4 % | 80.4 % | 15.3 % |
Blue | 370 | 99.5 % | 99.5 % | 99.2 % | 96.8 % | 97.6 % | 48.9 % |
yellow | 160 | 95.0 % | 94.4 % | 94.4 % | 92.5 % | 94.4 % | 61.9 % |
orange | 34 | 94.1 % | 94.1 % | 97.1 % | 91.2 % | 94.1 % | 85.3 % |
Red | 10 | 90.0 % | 90.0 % | 90.0 % | 90.0 % | 90.0 % | 100.0 % |
The snippet went out of control due to problem A and submitted it in print ('YES')
(all capital letters) and received a penalty. E problem is not good.
** Problem Page **: A --Three-Point Shot ** <font color = # 808080> Gray Coder Correct Answer Rate **: 98.1% ** <font color = # 804000> Brown Coder Correct Answer Rate **: 99.5% ** <font color = # 008000> Green Coder Correct Answer Rate **: 99.6%
** It doesn't matter which is larger, $ X $ or $ Y $, you can use max
and min
to subtract the smaller one from the larger one to find the point difference. ** **
Note that the $ 3 $ point is exactly 'No'
. (Because it is in the sample, let's add a habit to check it firmly)
X, Y = map(int, input().split())
d = max(X, Y) - min(X, Y)
if d < 3:
print("Yes")
else:
print("No")
It is easier to hit using the absolute value abs
, so if you notice it immediately, this is better.
X, Y = map(int, input().split())
d = abs(X - Y)
if d < 3:
print("Yes")
else:
print("No")
** Problem page **: B --Orthogonality ** <font color = # 808080> Gray Coder Correct Answer Rate **: 94.9% ** <font color = # 804000> Brown Coder Correct Answer Rate **: 99.3% ** <font color = # 008000> Green Coder Correct Answer Rate **: 99.7%
Just implement it exactly as it is written and determine if the result is $ 0 $.
** You don't have to think about what the dot product is. Do exactly what it says. ** **
I used zip
because it's easy to hit. It is the same as accessing the array by $ 1 $ each with range (N)
. (See the code below)
N = int(input())
A = [*map(int, input().split())]
B = [*map(int, input().split())]
inner_product = 0
for a, b in zip(A, B):
inner_product += a * b
if inner_product == 0:
print("Yes")
else:
print("No")
#Same as this
for i in range(N):
inner_product += A[i] * B[i]
** Problem Page **: C --ABC Tournament ** <font color = # 808080> Gray Coder Correct Answer Rate **: 62.5% ** <font color = # 804000> Brown Coder Correct Answer Rate **: 93.6% ** <font color = # 008000> Green Coder Correct Answer Rate **: 98.5%
** If you are motivated, I will write a little more carefully tomorrow **
** First of all, the conclusion is that "there aren't many restrictions on this issue, so you can just simulate the tournament" in time. ** **
There are $ 2 ^ N $ players. The maximum of $ N $ is $ N = 16 $. That is, there are up to $ 2 ^ {16} = 65536 $ players.
The tournament will play only half of the remaining players per $ 1 $ round. And half of the players will survive.
So the total number of matches when $ N = 16 $ is $ 32768 + 16384 + 8192 ... + 4 + 2 + 1 = 65535 $ matches. At this level, even if you simulate it, you can afford to meet the time limit.
Use $ 2 $ two deque
s (double-ended queues).
--Enter the number of the survivors in the tournament survive
--Enter the number of the winner of the tournament winner
First, put $ 1 $ to $ 2 ^ N $ in ascending order in survive
, which manages the number of survivors in the tournament. That is, enter in the order of $ 1,2,3, ..., 2 ^ N -1, 2 ^ N $.
Continue the following operations until survive
reaches $ 2 $.
survive
, usepopleft ()
to take out $ 2 $ people from the left and battle them, and the winner with the highest rate will be append
from the right to winner
.survive
is empty, set survive = winner
and return to 1.Finally, if you print the $ 2 $ ** loser ** of survive
, it's AC. ** (Since we are looking for a runner-up, we will output the person who lost in the final match) **
from collections import deque
N = int(input())
#I want to simulate it according to the problem statement, so A[0]Is added without permission (anything is fine because it is not used)
A = [-1] + [*map(int, input().split())]
# 1,2,3,...,2^N-1,2^N is in from the left
survive = deque(range(1, 2 ** N + 1))
#Excluding the finals, N-Simulate the first round and reduce survive survival to 2 people
for _ in range(N - 1):
winner = deque()
while survive:
#Take out two people at a time (never survive 2)^Since there are x people, it will not be an error if you take it out of an empty que)
first = survive.popleft()
second = survive.popleft()
if A[first] > A[second]:
#Add the winners to the winner (winners are also sorted in ascending order, so you don't have to sort them later)
winner.append(first)
else:
winner.append(second)
survive = winner
first = survive.popleft()
second = survive.popleft()
if A[first] > A[second]:
#Output the loser
print(second)
else:
print(first)
Recommended Posts