ABC163 C problem with python3

ABC163 C Problem Management

A word memo

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.

My wrong answer

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.

point

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.

Correct code

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

Consideration

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.

At the end

If you memorize the pattern found in this discussion, you can use it to solve other problems.

Find the number of elements in each number for a list containing multiple numbers

Sometimes you can write with reflection using a list! I want to come up with.

Recommended Posts

ABC163 C problem with python3
ABC188 C problem with python3
ABC187 C problem with python
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
Solve ABC163 A ~ C with Python
ABC166 in Python A ~ C problem
Solve ABC168 A ~ C with Python
Solved AtCoder ABC 114 C-755 with Python3
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
Solve ABC158 A ~ C with Python
[AtCoder] Solve ABC1 ~ 100 A problem with Python
ABC147 C --HonestOrUnkind2 [Python]
[AtCoder commentary] Win the ABC165 C problem "Many Requirements" with Python!
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
Solve AtCoder ABC166 with python
ABC memorandum [ABC163 C --managementr] (Python)
Solve AtCoder ABC 186 with Python
ABC memorandum [ABC159 C --Maximum Volume] (Python)
Call C from Python with DragonFFI
Create Awaitable with Python / C API
ABC127 A, B, C Explanation (python)
Solve ABC166 A ~ D with Python
ABC memorandum [ABC161 C --Replacing Integer] (Python)
Solve ABC036 A ~ C in Python
ABC memorandum [ABC158 C --Tax Increase] (Python)
ABC128 A, B, C commentary (python)
ABC126 A, B, C Explanation (python)
Solve ABC037 A ~ C in Python
AtCoder Beginner Contest 174 C Problem (Python)
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
AtCoder ABC151 Problem D Speed comparison in C ++ / Python / PyPy
[AtCoder explanation] Control ABC164 A, B, C problems with Python!
[AtCoder explanation] Control ABC168 A, B, C problems with Python!
Beginner ABC154 (Python)
Beginner ABC156 (Python)
FizzBuzz with Python3
Solve ABC175 A, B, C in Python
Scraping with Python
Statistics with python
Scraping with Python
AtCoder ABC 174 Python
Python with Go
Algorithm in Python (ABC 146 C Binary Search
Twilio with Python
AtCoder ABC187 Python
Integrate with Python
I wanted to solve ABC160 with Python
Python beginner Atcoder memo @ KEYENCE 2020, ABC problem
[C] [python] Read with AquesTalk on Linux
Play with 2016-Python
Japanese file enumeration with Python2 system on Windows (5C problem countermeasure)
AES256 with python
Tested with Python
AtCoder ABC188 Python
Beginner ABC155 (Python)
python starts with ()
python C ++ notes