** Aim for a light blue coder! !! !! !! !! !! ** **
So [Guidelines for improving AtCoder, a competition pro taught by Red Coder [Intermediate Edition: Aim for Light Blue Coder! ]]( https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7 % B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% E5% 8E % BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F) (@ e869120)
AtCoder has collected 100 good educational questions that are appropriate for brown and green coders to achieve a light blue coder, or rating 1200, with a small number of questions.
100 past questions that beginners and intermediates should solve in this article`
Will be solved with ** Python **!
Thanks to @ e869120! !! !! !! !! !!
** Search all: List all ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part1 / 22] ** Full search: All enumeration to reduce the number of streets by devising ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part2 / 22] ** Full search: Bit full search ** [[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Full search: Permutation full search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part4 / 22] ** Binary search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part5 / 22] ** Depth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part6 / 22] ** Breadth-first search ** [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]
We will solve the following 4 questions!
24 ALDS_11_B --Depth-first search This is a basic problem. 25 AOJ 1160-How many islands are there? The number of connected components in the graph can be calculated by depth-first search. 26 AtCoder Beginner Contest 138 D --Ki Many tree structure problems use depth-first search. 27 JOI 2009 Qualifying 4-Thin ice migration Depth-first search is not just a tree structure, it is a problem that tells us. It can be solved using a recursive function.
・ I will write an article based on the following three points! ** ① About stacks and queues ** First of all, Kencho's article Master stacks and cues! ~ Special feature on ideas and uses ~ Read about ** Atmosphere About Stacks and Queues! ** **
** ② About DFS and graph ** Another article by Kencho DFS (Depth-first Search) Super Introduction! ~ Entrance to the world of graph algorithms ~ [Part 1] DFS (Depth-first Search) Super Introduction! ~ Entrance to the world of graph algorithms ~ [Part 2] Read about DFS and Graphs ** Understand the Atmosphere! ** **
** ③ After that, how to implement DFS in Python ** As The following sites were easy to understand, so these two sites ** ◆ For ordinary graphs or trees ** Algorithm in Python (depth-first search, dfs) ** ◆ For grid graph ** Implementing Depth-First Search (DFS) in Python-ATC001 ** Carefully ** Read about DFS and Graphs ** Deeply! ** **
If you have the premise of ①②③, you can learn it by actually moving your hands! !! !!
Supplement 1 DFS has two implementation methods, ** Recursive Ver ** and ** Stack Ver **. ** In this article, we will unify the implementation of Stack Ver! !! !! ** ** (Easy to apply to BFS? + Fast speed? + Doesn't stack overflow occur?)
Supplement 2
Input from this article (** Part 6 **)
input()→sys.stdin.readline().rstrip()
I'm changing to!
[Python] Competitive template [At Coder]
I also made an article for the template, so please use it if you like ~
Typical graph problem!
graph = {i:collections.deque() for i in range(1,N+1)}
Or
graph = {i:[] for i in range(1,N+1)}
** This is the graph template! ** **
It was my first time implementing DFS, I tried to implement it according to the above site ** I managed to implement it! ** ** The code is long, but ** the difficulty isn't that great! !! !! ** **
The point is these two lines! !! !!
seen[j] = 1
stack.append(j)
seen[g_NO] = 1
stack.append(g_NO)
~ How to remember ~
① ** I saw the housekeeper! ** (drama), so
Change seen to0 (False)→1 (True)!
② If you see the housekeeper, put it in stock! !! !!
** (The housekeeper saw the trash, so I put it in the trash can !!!) **
If you have this image in mind, you can write code with brain death at the time of implementation!
test.py
import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
n = I()
ukv = [LI() for _ in range(n)]
graph = {i:collections.deque() for i in range(1,n+1)} #1_indexed
for x in ukv:
u,k,*v = x
for y in v:
graph[u].append(y)
seen = [0]*(n+1) #1_indexed
stack = []
time = 0
seentime = [0]*(n+1) #1_indexed
donetime = [0]*(n+1) #1_indexed
def dfs(j):
global time
seen[j] = 1
stack.append(j)
time += 1
seentime[j] = time
while stack:
s = stack[-1]
if not graph[s]:
stack.pop()
time += 1
donetime[s] = time
continue
g_NO = graph[s].popleft()
if seen[g_NO]:
continue
seen[g_NO] = 1
stack.append(g_NO)
time += 1
seentime[g_NO] = time
for j in range(1,n+1):
if seen[j]:
continue
dfs(j)
for k,a,b in zip(range(1,n+1),seentime[1:],donetime[1:]):
print(k,a,b)
I don't need to write def dfs (), but I tried to make it def so that it is easy to understand with the DFS description!
Also, the graph problem
I think most of the time it starts with "1" instead of "0"
Unify the entire code with 1_indexed!
I also tried using global for the first time, but I see! It feels like!
Another thing I was aware of when writing the code was
** I used continue as much as possible to prevent running code below the conditions to improve readability! ** **
DFS tends to be particularly nestled! (= Tends to be complicated = Bugs are more likely to occur!)
** The housekeeper saw! (Second time)**
Typical grid graph problem! The problem and the way of thinking of a normal graph are the same! I referred to the above site, but ** I was surprised! ** ** ** The housekeeper saw! (Third time)**
test.py
import collections,itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
while 1:
w,h = LI()
if w==h==0:
break
ans = 0
c = [LI() for _ in range(h)]
seen = [[0]*w for _ in range(h)]
stack = []
dhdw = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]
def dfs(H,W):
seen[H][W] = 1
stack.append([H,W])
while stack:
sh,sw = stack.pop()
for dh,dw in dhdw:
nh,nw = sh+dh,sw+dw
if not(0<=nh<=h-1) or not(0<=nw<=w-1) or seen[nh][nw] or c[nh][nw]==0:
continue
seen[nh][nw] = 1
stack.append([nh,nw])
for H,W in itertools.product(range(h),range(w)):
if seen[H][W] or c[H][W]==0:
continue
ans += 1
dfs(H,W)
print(ans)
26 AtCoder Beginner Contest 138 D - Ki Difficulty:923 ** I couldn't solve it at first sight! !! !! ** ** I stumbled on the amount of calculation and stumbled on the idea of roots! However, from now on, there will be a ** "tree" ** that can solve similar problems! !! !!
These two points are the points!
--Think of trees as undirected graphs --From the problem statement, the root of this whole tree is apex 1
All the vertices below the root feel like adding reference root points ~ If you didn't become AC, please refer to this article! !! !! AtCoder Beginner Contest 138 D --Ki test cases are increasing after the contest (modified version)
** The housekeeper saw! (4th)**
test.py
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,Q = LI()
ab = [LI() for _ in [None]*(N-1)]
px = [LI() for _ in [None]*(Q)]
ans = [0]*(N+1) #1_indexed
graph = {i:collections.deque() for i in range(1,N+1)} #1_indexed
for a,b in ab:
graph[a].append(b)
graph[b].append(a)
for p,x in px:
ans[p] += x
seen = [0]*(N+1) #1_indexed
stack = []
def dfs():
seen[1] = 1
stack.append(1)
while stack:
s = stack.pop()
if not graph[s]:
continue
for j in range(len(graph[s])):
g_NO = graph[s].popleft()
if seen[g_NO]:
continue
seen[g_NO] = 1
stack.append(g_NO)
ans[g_NO] += ans[s]
dfs()
print(*ans[1:])
By the way, Described in Supplement 2 at the beginning
Input from this article (** Part 6 **)
input()→sys.stdin.readline().rstrip()
I'm changing to!
The cause of this is this problem w
I was struggling with TLE, but when I saw the code of someone who could do it,
sys.stdin.readline()
I'm using ...
When I tried using it for the time being, I was surprised that it became an AC!
Upon examination, it turns out that ** ʻinput ()` is extremely slow! !! !! ** **
Reference article
8 small differences in processing speed that Python should know
There is room for improvement in the code regarding the amount of calculation,
(For example, where you receive ʻab and px`)
It's AC, so no ~
** I couldn't solve this at first sight either! !! !! ** **
No way ** I saw the housekeeper! The problem that (seen) ** cannot be used! !! !! Past articles [Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22] The subset sum problem is also a problem that can be solved by DFS. ** The housekeeper saw! If (seen) ** isn't available, ** the housekeeper saw! The difficulty level is higher because you have to think about what will change to (seen) **!
--Part3 subsum problem: ** index and sum ** --This issue: ** Position at stack, past history **
** You have to solve a lot of difficult problems and get used to it! ** **
test.py
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
m = I()
n = I()
area = [LI() for _ in range(n)]
ans = 0
dndm = [[1,0],[-1,0],[0,1],[0,-1]]
stack = [] #Stacked position, past history
def dfs(i,j):
global ans
stack.append([[i,j],set()])
while stack:
[sn,sm],history = stack.pop()
ans = max(ans,len(history))
for dn,dm in dndm:
nn,nm = sn+dn,sm+dm
if not(0<=nn<=n-1) or not(0<=nm<=m-1) or area[nn][nm]==0 or ((nn,nm) in history):
continue
stack.append([[nn,nm],history | {(nn,nm)}])
for i,j in itertools.product(range(n),range(m)):
if area[i][j]==1:
dfs(i,j)
print(ans)
history | {(nn,nm)}
of
| is a union! (Also a bitwise OR)
Also,
& is the intersection! (Also a bitwise AND)
^ Is a set of either `! (Also a bitwise XOR)
Next time, I will solve the following 6 questions!
28 ALDS_11_C --Breadth-first search This is a basic problem. 29 AtCoder Beginner Contest 007 C --Breadth-first search The shortest path problem of a weightless graph can be solved by breadth-first search. 30 JOI 2011 Qualifying 5-Cheese 31 JOI 2012 Qualifying 5-Illuminations The implementation is a little heavy, but if you do your best, you can solve it. 32 AOJ 1166 --Maze and order The implementation is a little heavy. 33 AtCoder Beginner Contest 088 D --Grid Repainting If this is solved, you can think that you are accustomed to breadth-first search.
Part6/22 end!
Recommended Posts