This page is created mainly for Python users who feel that A and B problems of AtCoder Beginner Contest (ABC) can be solved but C problem is difficult, starting with AtCoder. Did. We have briefly summarized the ideas of constraints and computational complexity, and the ideas you should know based on constraints and computational complexity.
If you have participated in ABC several times, you may have seen the commentary with computational complexity orders such as ** $ O (N ^ 2) $ ** and ** $ O (NlogN) $ **. There may be. To be honest, even if this is written, there are many people who do not understand what they mean or where the log comes from.
This idea of computational complexity order is on the page of ** Kenchon-san **, who is famous in the competitive programming world. ~ Where does the log come from ~](https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0)
You can roughly estimate in advance how long it will take to execute the calculation.
It will be like.
For a detailed explanation of the computational complexity order, please refer to the above Kenchon-san's page, but the concept of computational complexity order is the calculation speed. Can be estimated and becomes important after ABC's C problem (especially in Python). Let's roughly think about the amount of calculation.
To briefly explain the amount of calculation, ** "As the input size ** $ n $ ** increases, the execution time will increase proportionally by this amount." ** It becomes an index.
First, let's consider the following problems with concrete examples.
Takahashi, a first grader who loves to add numbers, always adds 1 + 2 + 3 ... At one point, Takahashi decided to add integers from 1 to ** $ n $ **. What is the sum of the integers from 1 to ** $ n $ **?
This problem can be solved by simply adding 1 to ** $ n $ **. The actual writing is as follows.
python
n = int(input())
ans = 0
for i in range(1, n+1):
ans += i
print(ans)
Now let's think about the complexity of this code, but it's simple. Since it took "1 + 2 + ..." and ** $ n $ ** times of steps, the amount of calculation is considered to be ** $ O (N) $ **. This means that as the input size ** $ n $ ** increases, the number of calculation steps increases in proportion to ** $ n $ **.
Next, let's consider the following problems.
Takahashi, a second grader who loves to multiply numbers, is tired of calculating multiplication tables. Therefore, Takahashi created a new multiplication table with arbitrary natural numbers ** $ n $ ** and vertical and horizontal ** $ n $ × $ n $ ** squares. The new multiplication table has 1, 2 ... ** $ n $ ** -1, ** $ n $ ** steps both vertically and horizontally, for example, ** (11, 10) ** squares. The number in is 11 × 10 and is ** 110 **. Takahashi-kun, who made the new multiplication table, remembered that he also liked adding, so he decided to add all the numbers in the table. What is the sum?
This problem can be solved by using a for statement inside a for statement. The actual writing is as follows.
python
n = int(input())
ans = 0
for i in range(1, n+1):
for j in range(1, n+1):
ans += i * j
print(ans)
Considering the amount of calculation of this code, it becomes ** $ O (N ^ 2) $ **. Using a for statement in this for statement is called a double loop, and the flow of movement is
python
# n = 100
# i =When 1
ans += 1 * 1
ans += 1 * 2
ans += 1 * 3
And when the second loop is over
python
# n = 100
# i =When 1
ans += 1 * 99
ans += 1 * 100
# i =Become 2
ans += 2 * 1
ans += 2 * 2
... and continue until i = 100, j = 100. In this way, the number of steps takes ** $ n × n $ ** times, so considering the amount of calculation, As the input size ** $ n $ ** increases, the number of calculation steps increases in proportion to ** $ n ^ 2 $ **, resulting in ** $ O (N ^ 2) $ **.
Let's consider the next problem in this flow.
Third grader Takahashi decided to make multiplication tables because multiplication tables were not enough. The multiplication table is the sum of length, width and height, and there are ** $ n $ × $ n $ × $ n $ ** squares. The length, width, and height are arbitrary natural numbers ** $ n $ **, and the steps are 1, 2 ... ** $ n $ ** -1, ** $ n $ **, respectively. The number in the box of ** (3, 4, 9) ** is 3 × 4 × 9, which is ** 108 **. Takahashi-kun, who created the multiplication table, remembered that he also liked adding, so he decided to add all the numbers in the table. What is the sum?
This problem can be solved with a triple loop that uses a for statement inside the for statement and then uses the for statement in it. The actual writing is as follows.
python
n = int(input())
ans = 0
for i in range(1, n+1):
for j in range(1, n+1):
for k in range(1, n+1):
ans += i * j * k
print(ans)
As you can see, considering the amount of calculation of this code, it becomes ** $ O (N ^ 3) $ **, and if the input size ** $ n $ ** increases, it becomes ** $ n ^. Since the number of calculation steps increases in proportion to 3 $ **, it becomes ** $ O (N ^ 3) $ **.
In this way, the amount of calculation is ** $ O (N) $ ** for one for statement, ** $ O (N ^ 2) $ ** for a double loop, and ** $ for a triple loop. As the number of loops increases, such as O (N ^ 3) $ ** ..., the amount of calculation increases as the number of loops increases.
By the way, if there are just two for statements instead of multiple loops, it will be ** $ O (N) $ ** instead of ** $ O (N ^ 2) $ **. This is because when considering the amount of calculation, the order other than the largest order is removed and the coefficient is ignored. For details, please refer to the ** Kencho-san ** page introduced earlier.
Add the codes 1 to 100 below twice. Actually, this number of steps is 200 times, and in the case of a double loop, 10,000 steps are required when n = 100, so sensuously ** $ from ** $ O (N ^ 2) $ ** I think O (N) $ ** is reasonable.
python
n = 100
ans = 0
for i in range(1, 101):
ans += i
for i in range(1, 101):
ans += i
print(ans)
Now that the amount of calculation in the for statement is required, let's think about it with constraints.
Constraints are always written in the actual problem as shown below.
Constraints ・ ** $ 1 ≤ N ≤ 10 ^ 5 $ **
With this constraint, you can roughly understand whether the code you wrote will meet the time limit by considering it as the amount of calculation.
For example, the constraint ・ ** $ 1 ≤ N ≤ 10 ^ 7 $ ** At that time, this can be passed without exceeding the time limit if it is a for statement of ** $ O (N) $ **. However, in the case of ** $ O (N ^ 2) $ ** such as a double loop larger than ** $ O (N) $ **, the time limit will always be exceeded. (Because the number of steps that can be processed per second is about ** $ 10 ^ 8 $ ** times)
By the way, the time limit of ABC is 2 seconds, so in the case of ** $ O (N) $ **, it is better to think that ** $ N ≤ 10 ^ 7 $ ** is the limit.
Next is the constraint ・ ** $ 1 ≤ N ≤ 10 ^ 5 $ ** Then, this means that ** $ O (N) $ ** can easily pass, and even a computational amount such as ** $ O (NlogN) $ ** can be passed within the time limit (more on this later). .. However, in the case of ** $ O (N ^ 2) $ **, it cannot be passed because it exceeds ** $ 10 ^ 8 $ **, which is a guideline.
And the constraints ・ ** $ 1 ≤ N ≤ 10 ^ 3 $ ** At that time, it is finally possible to pass the calculation amount of ** $ O (N ^ 2) $ **.
There are also restrictions ・ ** $ 1 ≤ N ≤ 300 $ ** In that case, the amount of calculation of ** $ O (N ^ 3) $ ** can also be passed.
Once you know the amount of computation in this way, you can roughly check whether this code can be passed within the constraint. However, Python is a much slower language than other languages such as C ++, so the above conditions may not apply. Actually, ABC162-C was a problem of triple loop, but the constraint is ** $ 1 ≤ N ≤ 200 $ **, and the amount of calculation is The time limit may be exceeded despite ** $ O (N ^ 3logN) $ **. (It can be passed in other languages.)
In this way, Python needs to be more conscious of the amount of calculation than other languages.
Let's think based on the actual problem.
First, let's think about ABC154-C.
The problem is that given an array of ** $ n $ ** integers, output "YES" if there are no duplicates, and "NO" if there are duplicates. Simply put, you can find the answer by checking each array one by one using a double loop.
python
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
for j in range(i+1, n):
if a[i] == a[j]:
print("NO")
exit()
print("YES")
In this way, if there are duplicate integers, "NO" is output and exit () is used, and if there are no duplicate integers, the double loop ends and "YES" is output. (By the way, the amount of calculation is ** $ O (N ^ 2) $ ** because of the double loop)
But if you look at the constraints of this problem ・ ** $ 2 ≤ N ≤ 200000 $ ** In this case, ** $ O (N ^ 2) $ ** is not enough.
Then, with this constraint, I think that the amount of calculation can be solved with ** $ O (NlogN) $ ** or ** $ O (N) $ **.
If you sort the array in ascending or descending order, if there are duplicate numbers, they will be next to each other, so it seems that you will be asked for an answer by checking all the values next to each other after sorting. In Python, you can sort the array in ascending or descending order by using the sort method.
python
a = [5, 2, 3, 4, 3, 9]
a.sort() #ascending order
# 2, 3, 3, 4, 5, 9
a.sort(reverse=True) # reverse=True in descending order
# 9, 5, 4, 3, 3, 2
Since the amount of calculation of this sort method can be done with ** $ O (NlogN) $ **, the amount of calculation can be done with ** $ O (NlogN) $ ** by checking with the for statement after sorting. (Because it becomes ** $ O (NlogN + N) $ ** and only the highest order is considered)
The actual release is as follows.
python
n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n-1):
if a[i] == a[i+1]:
print("NO")
exit()
print("YES")
In this way, if the constraint is ** $ 10 ^ 5 $ **, it will be easier to consider after the C problem by being aware that ** $ O (N ^ 2) $ ** will not be in time. Also, like the sort method this time, it will be necessary to know how to reduce the amount of calculation.
The above is a rough introduction of the for statement, mainly about the amount of calculation. If there is a for statement in the for statement, the amount of calculation is ** $ O (N ^ 2) $ **, and the amount of calculation of the sort method is ** $ O (NlogN) $ **. You may not get used to it at first, but as you practice, you will naturally remember it.
Depending on the problem, there are many ways to reduce the amount of calculation, such as changing the linear search to a two-minute search to reduce the amount of calculation, or finding the partial sum of the array efficiently by the scooping method or the cumulative sum. By remembering these things, you will gradually be able to solve ABC's C problem.
As a way to solve ABC's C problem, I think that the key to devotion is to practice a lot of past questions of C problem. Even if you do AC by yourself, you can know another method, the amount of calculation in this case, and how to write the code beautifully by reading the explanation or reading the code of another person. Also, since various explanations are written for each problem in an easy-to-understand manner, if it is difficult to read the official explanation or the code of another person, check it and know what to think.
The end has become messy, but this article is over. Thank you for your hard work!
Recommended Posts