I want to solve APG4b with Python (Chapter 2)

Introduction

Due to various circumstances, I will try to solve the APG4b problem published by Atcoder using Python. In Chapter 1, I tried to solve what volunteers have published, so from Chapter 2, I will try to solve the EX problem after reading it myself. I'm a beginner who only touched Python for about half a year at university, so I would appreciate it if you could tell me if there is something that can be shortened (or more efficiently). The goal is to create a code that "solves problems efficiently". Also, due to time constraints, if AC appears in the EX test, I will just read the model answer briefly and will not rewrite it.

2.01. How to write a loop and range for statement

** How to write a loop ** example

a = int(input())
data = list(map(int,input().split()))

answer = 0

for i in range(len(data)):
  if data[i] == a:
    answer += 1
  
print(answer)

** Range for statement ** example

a = [1,3,2,5]

for i in a:
  print(i)

At the head family, there was a statement that "a for statement can be used even with a container type", but I wondered "what is a container type ...?", So I looked it up. I wonder if the type that stores each element such as list and dict together is a container type ...? Is it something like calling an int or str a data type? With that in mind, I'll leave it here.

** Detailed story ** About proper use of loops

--When you want to process all the elements of the array → Range for statement -When processing repeatedly a certain number of times other than the conditions of ↑ → for statement --Other cases → While statement

The first thing I thought was "When do you use the While sentence ...?" When I used it at university, I was turning the While statement with a boolean type variable as a flag, but is this method actually used? I was wondering and fluttering.

** Cases where the While statement is suitable **

n = int(input())

count = 0

while n > 0:
  if n % 2 > 0:
    break
  n /= 2
  count+=1

print(count)

Useful "only while certain elements meet the conditions". When I thought about it, I used it like that at university (treated like a flag).

EX16 --Find the same adjacent value

data = list(map(int,input().split()))

keep=0
flag=False

for i in data:
  if keep==i:
    flag=True
    break
  keep=i

if flag==True:
  print("YES")
else:
  print("NO")

2.02. Multiple loops

** Multiple loop ** Loop inside the loop. I've heard that it's not a very complimented way, but I'm sorry I can't remember the source. I had a chance to see the code written by other people before, but when it was looped multiple times, it sometimes took a long time to read "What is this intention ...?". Mainly due to my lack of ability! Hey! !!

for i in range(3):
  for j in range(3):
    print("i:{},j:{}".format(i,j))

** Example "Determine whether two arrays A and B of 3 elements contain the same element" **

A = list(map(int,input().split()))
B = list(map(int,input().split()))

answer = False

for i in range(3):
  for j in range(3):
    if A[i]==B[j]:
      answer = True

if answer == True:
  print("YES")
else:
  print("NO")

Certainly, you could see duplicate array elements without multiple loops. From a readability point of view, I wrote it with brain death, thinking that it would be easier to understand.

** Multiple loop break / continue **

--You can break out of a one-step loop by using break / continue in multiple loops.

That's all there is to it. In the multiple loop of the example, it means "If you break / continue at" for j ~ ", you will go to" for i ~ "". It's a little difficult to understand, but it's hard to understand. Regarding this part, there is an easy-to-understand example in the head family.

** Missing subscript ** Regarding this, if you think "It is important to decide the variable name ...", I think that it is in line with the creator's intention. It's useless because "i" and "j" are hard to see at a glance. However, I always use it when turning for statements, always. By the way, in my first year, I feel like I was taught at university to "stop single-letter variables." Moreover, it seems that there were various issues to be submitted. Excuse me, teacher ...

EX17 --Shopping at a fruit shop

N,S = map(int,input().split())

A = list(map(int,input().split()))
P = list(map(int,input().split()))

count = 0
total = 0

for ap_price in A:
  for pin_price in P:
    total = ap_price + pin_price
    if total == S:
      count+=1
    else:
      total = 0

print(count)

2.03. Multidimensional array

A two-dimensional array I'm sorry, I'm totally ignorant about C ++, so when I read the original story, I could only think "Why would I write so much code just by creating an array?" When I touched C language (not ++) a long time ago, the word "allocate memory" came out, so I think that I am taking various steps to secure the capacity of the array. No, I don't really understand. Go back to Python.

example

data = []
for i in range(3):
  data.append(list(map(int,input().split())))

count = 0
for i in range(3):
  for j in range(4):
    if data[i][j] == 0:
      count+=1

print(count)

** Declaration ** In the above example, this is the part.

data = []
for i in range(3):
  data.append(list(map(int,input().split())))

Just append the standard input line converted to list to the list type variable data declared in advance. Is it okay to declare this?

access In terms of the two-dimensional array data created above

data[What number from the top][Number from the left]

** Learning size ** Since the "learning of size" shown at the head family was (vertical length, horizontal length), I will write how to import and check numpy. If it's easy to understand, you can only understand it ...

import numpy as np

#Create a two-dimensional array
data = []
for i in range(3):
  data.append(list(map(int,input().split())))

#Make it a NumPy array.shape
data = np.array(data)
print(data.shape)

** Concept of 2D array ** The head family is very easy to understand. However, it also says that it is not necessary in Python ... I don't feel like it, but it is knowledge that must be used in the first half of the second year of a certain university, so it is better to read it after all. One day, I heard from my seniors, "If you touch various languages, you can understand the language you touch for the first time in the atmosphere", so isn't it necessary for Python? It is important to read what you think as knowledge and dream of a useful day someday. It's important! !! !! !! !! !! !!

** Multidimensional array **

example I'm sorry I couldn't rewrite ... </ font> The input of this problem is multiple 3 × 3 format ○ × problems, but the blank line between the ○ × problems is inevitably included in the multidimensional array, and the last line cannot be read. It's packed ... As a habit of me, I stumble in places like this and spend infinite time, so once I'm calm, I'll start over. I mean, who are you apologizing for?

after that I haven't solved the above problem, so I'll do it later.

EX18 --Game Tournament

n,m = map(int,input().split())

lists = []
for i in range(m):
  lists.append(list(map(int,input().split())))
  
result = []
results = []
for i in range(n):
  for j in range(n):
    result.append("-")
  results.append(result)
  result = []
  
for i in lists:
  win = i[0]
  lose = i[1]
  results[win-1][lose-1] = "o"
  results[lose-1][win-1] = "x"

for i in results:
  j=" ".join(i)
  print(j)
    

This is absolutely bad writing. Anyway, I improvised to strip off the AC. We will fix it at a later date along with the exercises above.

Refer to 2.04.

reference

Referencing one variable to another. Can this be done with Python? After a quick search, I found the concepts of "immutable" and "mutable". "Immutable" refers to strings, numbers, etc., and objects belonging to this concept cannot change the numbers of one variable to another like the original family. On the contrary, objects such as dictionaries and lists that belong to "mutable" can be rewritten from one variable to another like the head family. Really.

a = 3
b = a
#The number 3 of a is output
print(b)

b = 4
#In the case of the head family, the numerical value of a is replaced and 4 is output.
#However, since the numerical object is immutable, 3 is output without replacement.
print(a)


a_list=[1,2,3]
b = a_list

b[0] = 4
#If it becomes the main street, a_The 0th element of list is rewritten[4,2,3]become
#The objects in list are mutable, so replace them[4,2,3]Is output
print(a_list)

Was there such a mechanism? I did not know…… I wondered if all objects are mutable in C ++, but when I touched C (not ++) long ago, C language manages variables in memory. I feel like I've heard the story. No, I was studying Haskell at the same time ... I'm sorry I can't remember for a moment and my memory is cloudy, so I'm going back to Python.

** After this ** It's easier to understand if you read the original (and it seems to be different from Python) …… But is the mechanism here the same as Python and C ++? Python is an interpreted language and C ++ is a compilation language, isn't it? I only know whether or not to compile at runtime, but the difference between the two is that the basic behavior is the same, only the execution method is different ...? I will investigate further by myself later. I don't know.

EX19-Multiplication table scoring

A = []
for i in range(9):
  line = list(map(int,input().split()))
  A.append(line)
  
correct_count = 0
wrong_count = 0

def saiten(A,correct_count,wrong_count):
  for i in range(9):
    for j in range(9):
      if A[i][j] == (i+1)*(j+1):
        correct_count+=1
      else:
        wrong_count+=1
        A[i][j]=(i+1)*(j+1)
  return A,correct_count,wrong_count

A,correct_count,wrong_count = saiten(A,correct_count,wrong_count)

for i in range(9):
  line =[str(a) for a in A[i]]
  line=' '.join(line)
  print(line)
  
print(correct_count)

print(wrong_count)
    

Since "correct_count" and "wrong_count", which indicate the number of correct and incorrect answers, are immutable objects, the numerical values cannot be replaced in the "saiten ()" function that performs scoring. So return is returning the result. Since "A" in the two-dimensional array that stores the calculation result is a mutable object, it can be replaced in the function. So I haven't returned it.

I've used immutable and mutable terms that seem to be technical terms, but if all of this is wrong, it would be pretty ridiculous. It seems that if you misunderstand the meaning of "waroshi" in ancient texts as "very interesting" and use it a lot in front of a Japanese language teacher, you will be frowned upon. Do it once in your life.

2.05. Recursive function

--Calling the same function within a function is called "recursive call" --A function that performs recursion is called a "recursive function".

I learned this in my first year, but I don't remember using recursion since then. It seems that this is a difficult category at the head family, and it was written that "If you do not understand after reading the explanation, you can skip it." e? Is this the one you don't use much?

I only remember it a little, so I'll write the exercise code and remember it.

def sum(n):
  if n == 0:
    return 0
  
  s = sum(n - 1)
  return s + n

print(sum(2)) # 0 + 1 + 2 = 3
print(sum(3)) # 0 + 1 + 2 + 3 = 6
print(sum(10)) # 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

I don't know how to put it into words.

sum (n) is supposed to return return 0, that is, 0 when ʻif n == 0. The recursive operation is performed with the following s = sum (n -1)`. The number obtained by subtracting 1 from n is pushed into the recursion call, and when n becomes 0, the recursion is terminated and the calculation is performed ...?

I understand the feeling of this function, but it is difficult to write it. Let's make a bullet point.

** For sum (2) **

[1st loop] ** n = 2 **, so the if statement is a path. s = sum (n -1) becomes s = sum (1). Recursion here.    ⬇︎ [2nd loop] ** n = 1 **, so if minutes are passes. s = sum (n -1) becomes s = sum (0). Recursion here.    ⬇︎ [Third loop] Go to the if statement with ** n = 0 **. 0 is returned by return.    ⬇︎ [2nd loop] s = sum (n -1) is the value returned in the 3rd loop ** s = 0 **. Since ** n = 1 **, do return s + n and return 1.    ⬇︎ [1st loop] s = sum (n -1) is the value returned in the 2nd loop ** s = 1 **. Since ** n = 2 **, do return s + n and return 3. the end.

That's what it is. This is my feeling. No, this is difficult to see for the first time. It seems to be fun to solve such problems, but is it okay for readability when it is used in actual battles? At my level, it's difficult to do without itemizing, but if you're an experienced person, can you tell at a glance? I have to devote myself ...

** After this ** Let's read the head family. Okay (not). I was a little difficult. However, in terms of content, I did a little in the algorithm class in the first half of the second year. To be honest, it may be better to read the contents of the head family as a textbook rather than as an actual battle. It may be better to read in an atmosphere like "There is such a way". But if I were to do it, I would just put up if statements and flags ... I can't think of it at all.

EX20-Number of reports

n = int(input())
read_line = list(map(int,input().split()))

p = []
for i in range(n):
  if i == 0:
    p.append(-1)
    continue
  p.append(read_line[i-1])
  
key = list(dict.fromkeys(p))
children={}

for i in key:
  value_list = []
  for j in range(n):
    if i == p[j]:
      value_list.append(j)
  children[i]=[]
  for k in value_list:
    children[i].append(k)

def count_report_num(chlidren,x):
  
  if children.get(x)==None:
    return 1
  
  sum = 0
  for i in children[x]:
    sum += count_report_num(chlidren,i)
  sum+=1
  return sum
    
    
for i in range(n):
  print(count_report_num(children,i))

I couldn't understand the behavior of recursion, so I referred to the model answer ... Also, it seems that you can add child elements to the array with c ++, but I did not know how to do it in Python, so I decided to execute it with dict type. It was difficult.

2.06. Computational complexity

--About "** order method **" that estimates the amount of calculation of the program

Carefully read the explanation of the head family. It was very easy to understand. This is also something I will do in the first half of the second year of a certain university, so I thought it would be useful.

--for sentence N if it is single, N ^ 2 if it is double --Log can be used in the case of "How many times can a specific number N be divided by 2?" --Speed (slowest order) [O (1) <O (logN) <O (N) <O (NlogN) <O (N ^ 2) <O (2 ^ N)]

EX21 --Estimation of Computational Complexity

I have an answer to this, and I don't have to rewrite it (comment out only), so I wonder if I don't have to write it.

Recommended Posts

I want to solve APG4b with Python (Chapter 2)
I want to solve APG4b with Python (only 4.01 and 4.04 in Chapter 4)
I want to debug with Python
I wanted to solve ABC160 with Python
I want to analyze logs with Python
I want to play with aws with python
I wanted to solve ABC172 with Python
I want to use MATLAB feval with python
I want to make a game with Python
I want to use Temporary Directory with Python2
I want to write to a file with Python
I want to solve Sudoku (Sudoku)
I want to handle optimization with python and cplex
I tried to solve the soma cube with python
I want to inherit to the back with python dataclass
I want to work with a robot in python.
[ML Ops] I want to do multi-project with Python
I tried to solve the problem with Python Vol.1
I want to run a quantum computer with Python
I tried to solve AOJ's number theory with Python
I want to do ○○ with Pandas
I want to be able to analyze data with Python (Part 3)
I want to specify another version of Python with pyvenv
I wanted to solve the Panasonic Programming Contest 2020 with Python
I want to be able to analyze data with Python (Part 4)
I want to be able to analyze data with Python (Part 2)
I want to automatically attend online classes with Python + Selenium!
[Python] I want to use the -h option with argparse
I want to detect objects with OpenCV
I want to blog with Jupyter Notebook
I want to use jar from python
I want to build a Python environment
I want to pip install with PythonAnywhere
I wanted to solve ABC159 in Python
I tried to solve TSP with QAOA
I tried to solve the ant book beginner's edition with python
I want to use a wildcard that I want to shell with Python remove
I want to know the weather with LINE bot feat.Heroku + Python
I want to monitor UNIQLO + J page updates [Scraping with python]
I want to output the beginning of the next month with Python
I read "Reinforcement Learning with Python: From Introduction to Practice" Chapter 1
I wanted to solve the ABC164 A ~ D problem with Python
[Introduction] I want to make a Mastodon Bot with Python! 【Beginners】
I read "Reinforcement Learning with Python: From Introduction to Practice" Chapter 2
I want to do Dunnett's test in Python
Solve AtCoder 167 with python
I want to do it with Python lambda Django, but I will stop
I want to analyze songs with Spotify API 2
I want to tweet on Twitter with Python, but I'm addicted to it
I want to memoize including Python keyword arguments
I want to create a window in Python
I want to email from Gmail using Python.
How to write offline real time I tried to solve E11 with python
Try to solve the man-machine chart with Python
[Python] I want to manage 7DaysToDie from Discord! 1/3
I want to mock datetime.datetime.now () even with pytest!
I want to display multiple images with matplotlib.
I want to knock 100 data sciences with Colaboratory
I wanted to install Python 3.4.3 with Homebrew + pyenv
I want to be an OREMO with setParam!
I tried to get CloudWatch data with Python