Now that it's a tle, think about where and how to change it. When it comes to tle, it's easy to think that it was a correct answer if there was no time limit, but the mistake is wrong. Let's be aware of building an algorithm considering the amount of calculation.
N=int(input())
boss_list=list(map(int,input().split()))
num=0
for i in range(1,N+1):
for j in range(i-1,N-1):
if boss_list[j]==i:
num+=1
print(num)
num=0
The wrong answer algorithm is Checks whether the boss's number is 1 for all employees from employee numbers 2 to N, and outputs the number of matches. Checks whether the boss's number is 2 for all employees with employee numbers 3 to N, and outputs the number of matches. ... Checks whether the boss's number is N-2 for all employees with employee numbers N-1 to N, and outputs the number of matches. Checks whether the boss's number is N-1 for all employees with employee numbers N to N, and outputs the number of matches. It has a double repeating structure. There is a lot of waste in this way of thinking.
Since the for statement that repeats about N times is used twice, the order becomes $ O \ left (N ^ {2} \ right) $ and becomes tle. The constraint is $ 2 \ leqq N \ leqq 2 \ times 10 ^ {5} $, so I want to keep the order to $ O \ left (N \ right) $. Since the output must be repeated N times, we aim to describe it in a single layer N times in a for statement.
You can reduce iterative processing by using lists well. In this case, if you create a list with N elements and store the number of subordinates with employee number x in the xth position, you can write the code as follows.
N = int(input())
A = list(map(int, input().split()))
result = [0] * N
for a in A:
result[a - 1] += 1
print('\n'.join(map(str, result)))
I was able to write a program concisely by using the list this time, but when is it effective? When you want to retrieve the number of each numerical value as an element for list A containing multiple numerical values, create a new list B containing a lot of 0s, and the xth number in list B is the numerical value x. It is good to store how many are included. An easy-to-understand example is given below. I want to find out how many numbers are included in the list A = [3,2,1,2,3,2,3,1] containing numbers from 1 to 3. At this time, if a new list B = [0] * 3 is prepared and the following processing is performed, the data to be obtained is stored in B.
A=[3,2,1,2,3,2,3,1]
B=[0]*3
for i in A:
B[i-1]+=1
print(B)
#At this time B[2,3,3]Will be. 1 included in A,2,The number of 3 was obtained respectively.
If you memorize the pattern found in this discussion, you can use it to solve other problems.
Sometimes you can write with reflection using a list! I want to come up with.
Recommended Posts