[AtCoder explanation] Control ABC188 A, B, C problems with Python!

** 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

table of contents

ABC188 Summary Problem A "Three-Point Shot" B problem "Orthogonality" C problem "ABC Tournament"

ABC188 Summary

Total number of submissions: 7831

performance

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

Correct answer rate by color

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 %

Brief commentary

A problem (7698 people AC) "Three-Point Shot"
`max (A, B) --min (A, B)` should be determined if it is less than $ 3 $. Alternatively, the absolute value of the difference, `abs (A --B)`, can be used for judgment.
B problem (7542 people AC) "Orthogonality"
Let's implement it as written.
C problem (6135 AC) "ABC Tournament"
This is also a problem to implement as written. Since the maximum is $ N = 16 $, the maximum number of participants is $ 2 ^ 16 = 65536 $. So you can simulate it in time.
D problem (2510 AC) "Snuke Prime" [not explained in this article]
You can't simulate $ 1 $ days at a time, as the maximum number of days is $ 10 ^ 9 $. For this kind of problem, it is easier to use a technique called ** "event sorting" **. Specifically, the events "$ a_i $ daily $ + c_i $ yen" and "$ b_i + 1 $ daily $ -c_i $ yen" are sorted by date. After that, you can solve it by looking at the events in order and simulating them. It can be solved by imos method + coordinate compression, but it is very troublesome.
E problem (1795 people AC) "Peddler" [not explained in this article]
Follow the
graph in ascending order from $ 1 $ to $ N $ to update the lowest gold prices in cities that can be visited before $ i $.
F problem (480 people AC) "+ 1-1x2" [Not explained in this article]
Memoization recursion. If you omit unnecessary actions, you need to visit fewer numbers, so you can do something like a simulation in time. By the way, it is almost the same as [AGC044-A "Pay to Win"](https://atcoder.jp/contests/agc044/tasks/agc044_a).
### The result of me ![screenshot.103.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/595910/401d58eb-6d87-bae9-b5db-d38ea904cd20.jpeg)

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 A "Three-Point Shot"

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

Implementation

** 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)

code

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 B "Orthogonality"

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

Implementation

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. ** **

code

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]

C problem "ABC Tournament"

** 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 **

Consideration

** 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.

Implementation

Use $ 2 $ two deques (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 $.

  1. From 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.
  2. When 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) **

code

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