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

2020/12/16 Update: Corrected the explanation of duplicate combinations of C problem a little carefully Added a pattern that uses the factorial function of the math module to the pattern that implements the function that finds the combination of C problems. Fixed incorrect display of C problem combination due to incorrect notation

** AtCoder Beginner Contest 185 ** ** 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 leave a comment or Twitter! ** ** Twitter: u2dayo

** LGTM **, I'm very happy to secretly

table of contents

ABC185 Summary Problem A "ABC Preparation" B problem "Smartphone Addiction" C problem "Duodecim Ferra"

ABC185 Summary

Total number of submissions: 7478

Promotion: I made an app called "AtCoderFacts"

I made an app called "AtCoderFacts". You can see the "correct answer rate for each rate" and "performance guideline" that we always do in this article.

That's all for now, but we plan to add more features in the future. Please use it.

** Link: https://app.atcoder-facts.com/ **

performance

Performance AC Score time Ranking(Within Rated)
200 AB---- 300 71 minutes 5827(5641)Rank
400 AB---- 300 17 minutes 4879(4693)Rank
600 ABC--- 600 36 minutes 4046(3862)Rank
800 ABCD-- 1000 85 minutes 3154(2973)Rank
1000 ABCD-- 1000 46 minutes 2321(2141)Rank
1200 ABCD-F 1600 93 minutes 1639(1461)Rank
1400 ABCD-F 1600 52 minutes 1129(952)Rank
1600 ABCDEF 2100 92 minutes 747(587)Rank
1800 ABCDEF 2100 65 minutes 489(338)Rank
2000 ABCDEF 2100 52 minutes 312(179)Rank
2200 ABCDEF 2100 41 minutes 201(87)Rank
2400 ABCDEF 2100 35 minutes 126(39)Rank

Correct answer rate by color

color Number of people A B C D E F
Ash 2861 98.0 % 68.4 % 31.7 % 20.8 % 1.4 % 3.9 %
tea 1420 99.3 % 95.6 % 74.9 % 69.8 % 4.2 % 15.5 %
Green 1062 99.8 % 98.6 % 92.9 % 92.9 % 13.2 % 44.4 %
water 685 99.7 % 99.1 % 98.1 % 98.4 % 43.9 % 90.1 %
Blue 345 99.7 % 99.7 % 99.7 % 99.7 % 80.0 % 98.0 %
yellow 151 97.3 % 96.7 % 96.0 % 95.4 % 90.1 % 98.0 %
orange 27 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 100.0 %
Red 9 77.8 % 77.8 % 88.9 % 88.9 % 100.0 % 100.0 %

Brief commentary

A problem (7332 people AC) "ABC Preparation"
`min (A)`.
B problem (5993 people AC) "Smartphone Addiction"
It is complicated, but if you simulate it as written, it can be solved with the computational complexity $ O (M) $.
C problem (4326 people AC) "Duodecim Ferra"
Duplicate combination. For Python 3.8, you can use the `comb` function of the` math` module. (Cannot be used with PyPy 7.3.0)
D problem (3882 people AC) "Stamp" [not explained in this article]
The length of the stamp should be the same as the length of the shortest continuous white square section. If you make it longer than that, you will not be able to press that section. It is permissible to double-press the red square, so it takes $ 1 $ to fill a white square section in red by dividing the length of that section by the length of the stamp and rounding up to the nearest whole number. I will. You can find this for the all-white square section and add it.
E problem (1006 people AC) "Sequence Matching" [not explained in this article]
[Editing distance](https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2) itself. ** "Train your problem-solving skills! You can just write the dynamic programming method on page 78 of "Algorithms and Data Structures" (Kenchon book) ** as it is.
F problem (1994 AC) "Range Xor Query" [Not explained in this article]
I don't like the word "just do", but I really just paste the segment tree. It's a good idea to use ACLs or have a library of abstract seg trees.

Results of me (Unidayo) (reference)

screenshot.45.jpg

It was completely completed for the first time.

Problem A "ABC Preparation"

** Problem page **: A --ABC Preparation ** <font color = # 808080> Gray Coder Correct Answer Rate **: 98.0% ** <font color = # 804000> Brown Coder Correct Answer Rate **: 99.3% ** <font color = # 008000> Green Coder Correct Answer Rate **: 99.8%

code

A = [*map(int, input().split())]
print(min(A))

Problem B "Smartphone Addiction"

** Problem page **: B --Smartphone Addiction ** <font color = # 808080> Gray Coder Correct Answer Rate **: 68.4% ** <font color = # 804000> Brown Coder Correct Answer Rate **: 95.6% ** <font color = # 008000> Green Coder Correct Answer Rate **: 98.6%

Consideration

Suppose you have $ 2 $ time $ t_0, t_1 $ ($ t_0 <t_1 $). The elapsed time is calculated by $ t_1 --t_0 $.

The problem statement says that the battery will increase or decrease at time $ n + 0.5 $. As you can see by drawing a number line, this means that it will increase or decrease every $ 1 $ second.

The time can be up to $ 10 ^ 9 $, but the number of cafes can be up to $ 1000 $. "Elapsed time from leaving a cafe to the next cafe" and "Cafe staying time" can be calculated by subtracting $ O (1) $, so if you simulate it, the amount of calculation is $ O (M) $. You can solve the problem.

Implementation

The battery can't be just $ 0 $. The judgment is $ 0 $ ** "less than or equal to". It is not "less than". ** **

Also, keep in mind that you can't have a $ 0 $ battery on your way home from the last cafe.

code

def solve():
    rem = N  #Remaining battery level
    prev = 0  #Time to leave the cafe (or start point) immediately before

    for _ in range(M):
        a, b = map(int, input().split())
        rem -= a - prev  #The battery will be depleted only for the elapsed time since you left the cafe (or start point) immediately before.
        if rem <= 0:
            #If the battery goes to 0 before you get to the cafe"No"(0 just out)
            return False
        rem += b - a  #The battery will be restored for the amount of time you stay in the cafe.
        rem = min(N, rem)  #Please note that the battery level does not exceed the upper limit N
        prev = b  #Leave the cafe at time b

    rem -= (T - prev)  #The excursion is until you get home at time T
    if rem <= 0:
        return False
    return True


N, M, T = map(int, input().split())

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

C problem "Duodecim Ferra"

** Problem page **: C --Duodecim Ferra ** <font color = # 808080> Gray Coder Correct Answer Rate **: 31.7% ** <font color = # 804000> Brown Coder Correct Answer Rate **: 74.9% ** <font color = # 008000> Green Coder Correct Answer Rate **: 92.9%

** If you are motivated, add a diagram and write it a little more carefully **

Consideration

When L = 12

If $ L = 12 $, the only obvious answer is $ 1 $, as you have to make $ 12 $ bars of $ 1 $ in length. ** (A bar with a length of $ 0 $ is useless) **

When L = 13

If $ L = 13 $, first make a $ 12 $ bar with a length of $ 1 $. Then, the length is over $ 1 $. You can use the extra length to choose only $ 1 $ out of $ 12 $ books to make them $ 2 $ in length. So the answer is $ 12 $.

When L = 14

If $ L = 14 $, you are free to allocate the extra $ 2 $ in length to the $ 12 $ bars. There are the following $ 2 $ patterns for how to stretch the bar.

  1. Make $ 1 $ sticks with a length of $ 3 $
  2. Make $ 2 $ sticks with a length of $ 2 $

The pattern $ 1 $ is $ 12 $. The pattern $ 2 $ is $ {} _ {12} C _ {2} = 66 $. So the total is $ 78 $.

When L = 15 or more

** Up to this point, it was possible to calculate by case, but it is impossible to solve by case because the number of patterns increases explosively as $ L $ increases. ** **

So I'll use another method.

To find ** like this problem ** "the number of groups ($ 12 $ sticks in this problem) to be assigned duplicates (the extra length in this problem)" ** , ** "Duplicate combination" ** can be used to calculate well.

** Reference link: ** Formulas and examples of duplicate combinations (balls, number of integer solutions) | Beautiful story of high school mathematics (The "Pattern to choose one or more" on this page is exactly the same as this problem.)

Examples of duplicate combinations

Take $ L = 15 $ as an example. The extra length is $ 15 -12 = 3 $.

There are $ 12-1 = 11 $ book dividers ** | ** and $ 3 $ circles ** ● **.

Create $ 11 + 3 = 14 $ free space ** □ ** to allocate ** | ** and ** ● **.

□□□□□□□□□□□□□□

From the $ 14 $ free space, choose the $ 11 $ location and place ** | **. As an example, let's assume that we have arranged the following:

□||||||||□□|||

Then, allocate ** ● ** to the extra $ 3 $ of space.

●||||||||●●|||

this is,

"Extend the first bar" by "the number of ● to the left of the first partition" "Extend the second bar" by "the number of ● between the first partition and the second partition" …… "Extend the 12th bar" by "the number of ● to the right of the 11th partition"

It represents that.

In the above arrangement, the $ 1 $ th bar is $ + 1 $ and the length is $ 2 $, the $ 9 $ th bar is $ + 2 $ and the length is $ 3 $, and the remaining bars are not stretched so the length is $ 1 $ Will be.

How to find in general

●: $ L -12 $ pieces |: $ 11 $ pieces Free space: $ (L -12) + 11 = L-1 $ pieces

** $ L --- Select $ 11 $ out of 1 $ of free space, set |, and assign ● to the remaining space **

So you can find it with $ {} _ {L-1} C _ {11} $. The combination can be calculated with $ O (N) $, so you can afford it.

Implementation

In the case of languages ​​such as C ++ where the range of integer values ​​that can be handled is limited, the correct answer will not be given due to overflow without some ingenuity. On the other hand, Python has no limit on the range of integer values ​​it can handle. Therefore, you can calculate normally without thinking about anything. It's the best.

Now let's move on to the implementation of combinatorial calculations. It depends a little on whether you're using Python 3.8.2 or PyPy 7.3.0.

For Python 3.8.2

For ** Python 3.8.2 **, you can use the comb function of the math module. Use this and you're done.

from math import comb
ans = comb(X + 11, 11)

For PyPy 7.3.0

** PyPy 7.3.0 is based on Python 3.6. So you can't use the comb function of the function added in Python 3.8. If you try to use it, you will be penalized with a run-time error (RE). ** **

So you just have to write the comb function as defined by yourself. You don't have to think about anything mathematically, just put the formula below that comes out when you look it up into your code.

 {}_n C_k =\frac{n!}{k!(n-k!)}

The factorial is $ 3 $ in this formula. You can calculate the factorial in the for loop, but it is easier to use the factorial function of the math module.

from math import factorial

def comb(n, k):
    return factorial(n) // (factorial(k) * factorial(n - k))

The factorial (200) calculated with the maximum value of the constraint is the following ** 375 digit large number **, but Python still calculates it without any problem.

>>> import math
>>> math.factorial(200)
788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000

>>> len(str(math.factorial(200)))
375

code

For the comb function in Python 3.8.2

Code for using the comb function of the math module in Python 3.8.2.

from math import comb

L = int(input())
X = L - 12
ans = comb(X + 11, 11)
print(ans)

When writing with the factoriral function

from math import factorial

def comb(n, k):
    return factorial(n) // (factorial(k) * factorial(n - k))

L = int(input())
X = L - 12
ans = comb(X + 11, 11)
print(ans)

When writing with 3 for loops

At first, I only included this code in the explanation, but I don't recommend this problem because it is less restrictive and you can use the factorial function.

def comb(n, k):
    ret = 1
    for i in range(1, n + 1):
        ret *= i
    for i in range(1, k + 1):
        ret //= i
    for i in range(1, n - k + 1):
        ret //= i
    return ret


L = int(input())
X = L - 12
ans = comb(X + 11, 11)
print(ans)

Recommended Posts