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

** A, B, C, D problems ** of ** AtCoder Beginner Contest 181 ** 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

[ABC181 Summary](# abc181-Summary) [Problem A "Heavy Rotation"](#a Problem heavy-rotation) [B problem "Trapezoid Sum"](#b problem trapezoid-sum) [C problem "Collinearity"](#c problem collinearity) [D problem "Hachi"](#d problem hachi)

ABC181 Summary

Total number of submissions: 6643

performance

Performance AC Score time Ranking(Within Rated)
200 AB---- 300 20 min 5056(4953)Rank
400 ABC--- 600 77 minutes 4179(4077)Rank
600 ABC--- 600 28 minutes 3435(3333)Rank
800 ABCD-- 1000 95 minutes 2647(2549)Rank
1000 ABCD-- 1000 60 minutes 1918(1822)Rank
1200 ABC-E- 1100 87 minutes 1324(1230)Rank
1400 ABCDE- 1500 83 minutes 873(789)Rank
1600 ABCDE- 1500 61 minutes 558(476)Rank
1800 ABCDE- 1500 44 minutes 345(269)Rank
2000 ABCDEF 2100 103 minutes 197(139)Rank
2200 ABCDEF 2100 72 minutes 104(66)Rank
2400 ABCDEF 2100 56 minutes 52(30)Rank

Correct answer rate by color

color Number of people A B C D E F
Ash 2714 99.0 % 84.1 % 43.0 % 18.0 % 1.4 % 0.1 %
tea 1228 99.8 % 99.7 % 85.8 % 61.5 % 4.2 % 0.1 %
Green 972 99.7 % 99.7 % 96.2 % 87.7 % 37.4 % 0.4 %
water 574 99.8 % 99.8 % 98.6 % 95.1 % 86.6 % 7.0 %
Blue 291 99.7 % 99.7 % 100.0 % 98.6 % 98.3 % 38.5 %
yellow 78 97.4 % 97.4 % 98.7 % 98.7 % 88.5 % 55.1 %
orange 22 95.5 % 95.5 % 100.0 % 100.0 % 95.5 % 81.8 %
Red 3 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 100.0 %

Brief commentary

A problem (6568 people AC) "Heavy Rotation"
The answer depends on whether the number of days is even or odd.
B problem (5936 people AC) "Trapezoid Sum"
The method of adding $ A $ to $ B $ in a straightforward manner is not in time. Using the arithmetic progression, the sum of each range can be calculated using a mathematical formula.
C problem (4329 people AC) "Collinearity"
$ 3 $ Make a judgment for all combinations of points in a heavy loop. The formula for judgment is high school mathematics. I googled.
D problem (3152 people AC) "Hachi"
"A certain integer is a multiple of 8" ⇔ "The last 3 digits of a certain integer are a multiple of 8". Try to make all possible last 3 digit candidates, and if you can make any one, it's OK.
E problem (1344 AC) "Transformable Teacher" [not explained in this article]
Fix the height of the teacher and sort the sequence of heights added to the students in ascending order. At this time, it is best to pair with the next person like $ (1, 2), (3, 4), (5, 6), ... $. For all teacher height candidates, find out what number the teacher is in by binary search. It can be solved by efficiently calculating the sum of the differences at that time using the cumulative sum.
F problem (230 people AC) "Silver Woods" [not explained in this article]
Obtain all "distance between a certain point and the upper straight line", "distance between a certain point and the lower straight line", and "distance between two points" in advance. Use UnionFind to connect the components in ascending order of distance. The answer is the distance when the upper straight line and the lower straight line have the same connected component.

Results of me (Unidayo) (reference)

screenshot.308.png

C and D problems have been googled. It was a little difficult because I was not good at implementing the E problem, but overall it was a fair result.

Problem A "Heavy Rotation"

** Problem page **: A --Heavy Rotation ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 99.0% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 99.8% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 99.7%

Consideration

If $ N $ is odd, it is " Black ", and if it is even, it is " White ". If the remainder of $ N $ divided by $ 2 $ is $ 0 $, it is an even number, and if it is $ 1 $, it is an odd number.

code

N = int(input())

if N % 2 == 1:
    print("Black")
else:
    print("White")

Problem B "Trapezoid Sum"

** Problem page **: B --Trapezoid Sum ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 84.1% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 99.7% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 99.7%

Consideration

As shown in the code below, the method of adding integers from $ A $ to $ B $ is TLE.

N = int(input())

ans = 0
for _ in range(N):
    a, b = map(int, input().split())
    for x in range(a, b + 1):
        ans += x

print(ans)

In order to make it in time, it is necessary to calculate the sum of each range with a single formula.

There are about $ 2 $ in mathematical formulas, but both are similar.

-$ (sum of integers from 1 to B)-(sum of integers from 1 to A--1) Find by $ --Use the formula of the sum of arithmetic progressions of the first term $ A $ number of terms $ B-A + 1 $, tolerance $ 1 $

This time, I will explain the simple former.

How to find the sum from 1 to x

$ S = (sum of 1 to x) $ is calculated by the following formula. This expression is always divisible into an integer.

S = \frac{x{(x+1)}}{2}

In code, it looks like this: Note that we use // (integer division) to truncate after the decimal point.

s = x * (x + 1) // 2

** This formula is very often used in competition pros. If you didn't remember it, it's always helpful to remember it at this opportunity. ** **

code

def calc(x):
#A function that returns the sum from 1 to x
    return x * (x + 1) // 2


N = int(input())

ans = 0

for _ in range(N):
    a, b = map(int, input().split())
    ans += (calc(b) - calc(a - 1))

print(ans)

C problem "Collinearity"

** Problem page **: C --Collinearity ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 43.0% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 85.8% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 96.2%

Consideration

The maximum number of points is $ 10 ^ 2 = 100 $, so it is sufficient to judge whether all three point combinations are on the same straight line or use a $ 3 $ heavy loop.

The condition that the $ 3 $ points are on the same straight line is that the following equation holds. (For details, leave it to Official commentary and Google search)

(x_2-x_1)(y_3-y_1) = (x_3-x_1)(y_2-y_1)

code

def judge():
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                x1, y1 = P[i]
                x2, y2 = P[j]
                x3, y3 = P[k]
                fx, fy = x2 - x1, y2 - y1
                sx, sy = x3 - x1, y3 - y1
                if fx * sy == sx * fy:
                    return True
    return False


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

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

if judge():
    print("Yes")
else:
    print("No")

D problem "Hachi"

** Problem page **: D --Hachi ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 18.0% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 61.5% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 87.7%

Consideration

When S is 1 or 2 digits

In the case of $ 1 $ digits, it cannot be sorted, so you can just judge whether it is divisible by $ 8 $.

In the case of $ 2 $ digits, you can judge whether it is "use as is" or "turn over" $ 2 $ pattern, which is divisible by $ 8 $.

When S is 3 digits or more

** "A certain integer is a multiple of 8" ⇔ "The last 3 digits of a certain integer are a multiple of 8" **. I'll leave the details elsewhere, because $ 1000 $ is a multiple of $ 8 $.

That is, if you can rearrange ** $ S $ freely and even the last $ 3 $ digits are a multiple of $ 8 $, you can make it a multiple of $ 8 $. ** **

There are only over $ 100 $ multiples of $ 8 $ in $ 3 $ digits. Therefore, it can be solved by ** "determine whether it can be made for multiples of $ 8 $ of all $ 3 $ digits" **.

Judgment method

For example, if you want the last 3 digits to be $ 112 $, you can make it if $ 1 $ is $ 2 $ or more and $ 2 $ is $ 1 $ or more in $ S $.

To make this judgment, you should count in advance how many $ 1 $ to $ 9 $ are included in $ S $.

Implementation

Counter when counting

When counting, it's easier to use the Counter in the collections module.

>>> from collections import Counter
>>> S = "181"
>>> cnt_first = Counter(S)
>>> cnt_first
Counter({'1': 2, '8': 1})  # '1'2 pieces,'8'There is one

How to make a multiple of 3 digits 8

for x in range(104,1000,8):
    #processing

Specify the argument of range as follows.

Starting point: $ 3 $ The smallest multiple of $ 8 $ in digits $ 104 $ End point: $ 1000 $ (less than) Steps: $ + 8 $ each

Now you can enumerate $ 104, 112, 120, ..., 984, 992 $.

code

from collections import Counter


def judge():
    if len(S) == 1:
        if int(S) % 8 == 0:
            return True
    elif len(S) == 2:
        if int(S) % 8 == 0 or int(S[::-1]) % 8 == 0:
            return True
    else:
        for x in range(104, 1000, 8):
            cnt_current = Counter(str(x))
            ok = True
            for key, val in cnt_current.items():
                if val > cnt_original[key]:
                    ok = False
            if ok:
                return True
    return False


S = input()
cnt_original = Counter(S)  #You can see how many letters 1 to 9 are in S

if judge():
    print("Yes")
else:
    print("No")

Digression

Official commentary is smarter to use Counter. I think you can do it this way.

We subtract between Counters and say that we can make it if it becomes empty.

Recommended Posts