We will explain how to solve ** C problem "Many Requirements" ** of ** AtCoder Beginners Contest 165 ** with ** Python 3 ** as carefully as possible.
It's been so long that I've split only the C problem.
I will explain in three ways.
--Use itertools.combinations_with_replacement () (easiest) --Create with queue recursion (highly versatile method) --Depth-first search (DFS) (Explanation PDF method, annoying)
ABC165C『Many Requirements』
** Problem page **: C --Many Requirements ** Difficulty **: ★★★★★★★★★★ (Difficult D problem level!) ** Type **: Brute force idea, depth-first search (other methods available), past exercises
First of all, it is difficult to read the problem statement and understand the meaning. Even if you understand the meaning, you need to think of making all the sequences and checking them. And even if you know that you are brute force, you can't solve it without knowing how to make a sequence.
To be honest, it's the difficulty of the difficult D problem.
After somehow deciphering the problem statement, it seems that what we want us to make is a sequence of $ N $ in length. The length $ N $ is 2-10. If the sequence meets the conditions, you will get a score, so I want you to give the maximum value of that score.
The numbers in the sequence are greater than or equal to $ 1 $ and less than or equal to $ M $. The upper limit of $ M $ is 1-10. And the number must be the same as or larger than the previous number. It means that the numbers should not decrease in the middle.
For example, suppose $ N = 4 $ and $ M = 3 $.
Let me give you an example of the allowed sequence.
Let me give you an example of a bad sequence. $ 1,1,3,2 $ ($ 2 $ is greater than $ 3 $, so you can't come after 3) $ 1,2,3,4 $ ($ 4 $ exceeds the upper limit $ M = 3 $) $ 0,1,2,3 $ ($ 0 $ is not good because it is over $ 1 $) $ 1,1,1 $ (length $ N = 4 $) $ 1,1,1,1,1 $ (same as above)
Finally, there are $ Q $ conditions. There are a maximum of 50 conditions, and one condition consists of four integers $ a, b, c, d $.
The condition is
($ b $ th of the created sequence)-($ a $ th of the created sequence) = $ c $
Is to be. If so, you will get a score of $ d $.
For example, the condition is
To give some examples of sequences, $ 1,1,2,3 $ and $ 1,2,3,3 $ will give you $ 5 $ points, but $ 1,2,2,2 $ and $ 2,2,3,3 I don't get $.
I'd like you to find the maximum value of the total score obtained by checking this for all conditions.
The only problem with this problem is to create all possible sequences and calculate each score to find the maximum value. Therefore, you can never solve it unless you realize that you can brute force.
Since the maximum length of the sequence is 10 and the maximum number is 10, I feel that there are not so many sequences that can be created. If you ask for the exact number as written in the PDF, it will be ~~ 20C10 = 184756 ~~ $ \ _ {19} C_ {10} = 92378 $. (Corrected on 5/3. Thank you @forzaMilan!)
And since the maximum number of conditions for getting points is 50, it seems that it will be in time even if you check all the sequences you made.
Well, even if you realize that you can brute force, you can't solve it unless you know how to make all the sequences.
The problem of creating such sequences and strings sometimes comes up, so you may understand it if you solve similar problems. However, if you don't know it, it will be difficult to come up with it during the contest.
There are several ways to create a sequence.
--Use itertools.combinations_with_replacement (easiest) --Create with queue recursion (highly versatile method) --Depth-first search (commentary PDF method)
The easiest way is to use the combinations_with_replacement () function of the ʻitertools` module. As I learned later, I can just use this function to enumerate the entire sequence of this problem.
The name is long and hard to remember, but it's a useful function. To use it, you need to import the ʻitertools` module.
combinations_with_replacement () is a function that enumerates "duplicate combinations". The difference from the usual "combinations" combinations () is that it allows you to select the same element multiple times.
There are two inputs: an "iterable" element and the number of times the element is retrieved (column length). "Iterable" is "iterable" in English, meaning "iterable". The ones that can be used after in in a for loop, such as "list", "tuple", "range () ", and "string".
The output is all "duplicate combinations" that can be made with the input conditions. Each output comes out in "order of input elements". This is important.
Let's see what is created with the for loop and print (). Let's assume that there are three elements, range (1,4), that is, (1,2,3), and the length is 2.
#Because it's long, comb_Import with the name rplc
from itertools import combinations_with_replacement as comb_rplc
for seq in comb_rplc(range(1, 4), 2):
print(seq)
(1, 1)
(1, 2)
(1, 3)
(2, 2)
(2, 3)
(3, 3)
It also includes those in which the same element appears multiple times, such as (1, 1) and (2, 2). Since the input is in the order of 1,2,3, there is no next number smaller than the previous number like (2, 1) and (3, 2).
Compare it with the usual combination combinations ().
from itertools import combinations
for seq in combinations(range(1, 4), 2):
print(seq)
(1, 2)
(1, 3)
(2, 3)
Certainly, there are no (1, 1) or (2, 2) that select the same element twice.
Try setting the input to "CBA". Like for, it is considered as three elements: " C ", " B ", and " A ".
for seq in comb_rplc("CBA", 2):
print(seq)
('C', 'C')
('C', 'B')
('C', 'A')
('B', 'B')
('B', 'A')
('A', 'A')
Since I input in the order of C, B, A, the output is also arranged in that order. Please note that they do not appear in the order of ABC.
The condition of the sequence created in this problem is that the next number is not less than the previous number. If you sort the inputs in ascending order, the outputs will also be in ascending order, so this condition will be met without permission.
Since the sequence length is $ N $ and the upper limit of the number is $ M $, combinations_with_replacement (range (1, m + 1), n) can be used to enumerate all possible sequences.
Import with an abbreviated name, such as from itertools import combinations_with_replacement as comb_rplc, to avoid cluttering your code.
from itertools import combinations_with_replacement as comb_rplc
n, m, q = list(map(int, input().split()))
#req is[[a1,b1,c1,d1],[a2,b2,c2,d2]……]It is a list of the list containing
req = [list(map(int, input().split())) for _ in range(q)]
ans = 0
#seq is a tuple of length n
for seq in comb_rplc(range(1, m + 1), n):
score = 0
for a, b, c, d in req:
#If the kth of the sequence written in the problem statement is an index, k-Note that it will be 1
if seq[b - 1] - seq[a - 1] == c:
score += d
ans = max(ans, score)
print(ans)
"with replacement" means "to replace". "replace" is more often used to mean "replace" or "replace", but that is not the case.
Suppose you have a ball with numbers in it. In a normal "combination" that is "without replacement", the removed balls are not returned to the bag. In the "with replacement" "duplicate combination", make a note of the number of balls taken out and then put them back in the bag.
It may be easier to remember this function if you understand the meaning in this way.
I was able to create a sequence of this problem with combinations_with_replacement (), but as the conditions become more complex, I have to implement it myself.
When you want to create all the character strings and sequences that satisfy certain conditions, there is a highly versatile method called "queue recursion".
As the name implies, it uses a data structure (array) called a queue. What a queue looks like is an array that "takes out what you put in first" (FIFO: First In, First OUT). This is a major one that comes out when you study algorithms.
It repeats taking the strings that are still in the process of being created from the queue, adding one character to the strings, and adding them to the queue.
Then, all the sequences you want to make are finally generated.
To use queues in Python, you need to import the deque () from the collections module.
"deque" is an acronym for "double-ended-queue" and is a data type called "double-ended queue". The pronunciation is "deck".
Deques can retrieve and add elements from either the beginning or the end. That is, it is upward compatible with stacks and queues.
There are two methods for adding and retrieving elements to the deque.
ʻAppend (): Append element to the right (end) ʻAppendleft (): Add an element to the left (first)
pop () Extract the right (end) element
popleft (): Extract the left (first) element
"Take out what you put in first" in the queue is paraphrased as "when putting in, from the right" and "when taking out, from the left".
In other words, if you use ʻappend ()to insert andpopleft ()` to extract, you can create a queue by itself.
In the case of a stack, "take out what you put in later", so when you take it out with ʻappend (), it is pop ()`.
Let's take a look at the pseudo-code style of queue recursion and see what it does.
from collections import deque
que = deque()
que.append(Initial state) # Initial stateを入れないと、while queを素通りします
while que:
Current state= que.popleft() #Take out from the beginning
#Do something
meet the if condition:
#Do something
else:
Next state=Current state+ α #In some cases, for for creates multiple "next states"
que.append(Next state) #Add to the end
while que means that if que is not empty, it will be judged as True, and if it is empty, it will be judged as False, so it will loop until the contents of que are empty.
If the conditions are met, an infinite loop will occur if no processing is performed without adding to the queue.
This will allow the queue to be restarted.
from collections import deque
#A function that calculates the score of a sequence
def calc(seq):
score = 0
for a, b, c, d in req:
if seq[b - 1] - seq[a - 1] == c:
score += d
return score
n, m, q = list(map(int, input().split()))
req = [list(map(int, input().split())) for _ in range(q)]
ans = 0
que = deque()
#The first in the sequence,[1]～[m]Will be queued up to
#Actually, this problem is at the beginning of the sequence[1]It can be solved by considering only the case of.
for i in range(1, m + 1):
que.append([i])
while que:
seq = que.popleft()
if len(seq) == n:
#Now that the length is n, calculate the score
score = calc(seq)
ans = max(ans, score)
else:
#The next number to add is that the lower limit is the last number in the current sequence and the upper limit is m.
for i in range(seq[-1], m + 1):
seq_next = seq + [i]
que.append(seq_next)
print(ans)
I will write how the contents of the queue change when m = 3 and n = 3.
[1], [2], [3](initial state) [2],[3],[1,1],[1,2],[1,3] [3],[1,1],[1,2],[1,3],[2,2],[2,3] [1,1],[1,2],[1,3],[2,2],[2,3],[3,3] [1,2],[1,3],[2,2],[2,3],[3,3],[1,1,1],[1,1,2],[1,1,3] [1,3],[2,2],[2,3],[3,3],[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3] …… (Omitted) [2,3,3],[3,3,3] [3,3,3] None (end)
You take out the one on the far left and add one number to it and add it to the right. In this way you can create all the sequences.
A length of 3 means that the sequence is complete, so we just calculate the score and do not add any new state to the queue. As a result, the queue will eventually be empty and you will not fall into an infinite loop.
This problem can be solved with the "put in from right and take out from right" stack instead of the "put in from right and take out from left" queue.
By the way, the stack can be a regular list instead of a deque. ʻAppend ()andpop ()` methods are also in the regular list.
However, basically it is recommended to treat deque () as a queue and solve it. There are three advantages.
--Deque works faster as the number of elements increases ――When using cues, it is sometimes useful that sequences and character strings appear in "dictionary order". --There are opportunities to use deques other than string / sequence enumeration, so it is advantageous to get used to it.
Queue recursion is "breadth-first search" (BFS) itself. Stack recursion results in "depth-first search" (DFS).
You can do either if you just make all the strings and sequences, but the order in which they appear is different.
The last is to use the depth-first search described in the official commentary PDF. Use "recursive function".
There's more you can do than queue recursion or stack recursion, but if you just want to create strings or sequences, queue recursion is enough.
The advantage of depth-first search
――Easy to implement "going processing" and "returning processing" ――I feel like I'm writing an algorithm if I can
The disadvantage is
--Recursive functions are hard to understand (don't try, feel and get used to) --In Python, it tends to get stuck in the upper limit of the number of recursion and become RE
The argument of the dfs function is the current sequence seq (tuple). The lower bound of the next number is seq [-1] because it is the last in the current sequence.
For example, suppose you add 3 to the sequence 1,1 to get 1,1,3. The next number to add must be 3 or greater, so (the lower limit of the next number) is the 3 we just added.
If the length of the current sequence is less than n, add (lower limit of numbers) to (upper limit of numbers m) and add all the new sequences again to dfs (the sequence you just created, the length of the sequence you just created, The minimum of the following numbers).
If the current sequence is 1,1,3 and the upper limit is $ M = 4 $, 1,1,3,3 1,1,3,4 Is passed to dfs.
When the length is n and it is completed, the score is calculated. When you get a score, update the maximum value with ʻans = max (ans, score)`. This is the same as a normal problem.
When all is done, all the maximum values will be returned to the code of the main body, so print this and you're done.
def dfs(seq):
#The return value is the maximum score ans for all sequences.
ans = 0
if len(seq) == n:
#Now that the sequence is complete, calculate the score
score_ret = 0
for a, b, c, d in req:
if seq[b-1] - seq[a-1] == c:
score_ret += d
return score_ret #Returns the score of this sequence
else:
#The sequence is not completed yet
for i in range(seq[-1], m + 1):
seq_next = seq + (i,) #Tuple of length 1(i,)Concatenate
score = dfs(seq_next) # seq_Returns the maximum score in all sequences derived from next
ans = max(ans, score) #Update maximum score
#Returns the maximum score
return ans
n, m, q = list(map(int, input().split()))
#req is[[a1,b1,c1,d1],[a2,b2,c2,d2]……]It is a list of the list containing
req = [list(map(int, input().split())) for _ in range(q)]
#Make sure you get the answer in the end. All the processing is done by the dfs method.
#If it is a list, I am afraid that I will rewrite the value by mistake somewhere, so I will make it a tuple
#You don't have to think about it except when the first is 1.(1,)I will only do
ans = 0
score = dfs((1,))
ans = max(ans, score)
print(ans)
I wrote several times that I don't have to think about it except when the first of the sequence is 1. In the depth-first search of code 3, only the beginning of 1 is actually searched completely.
The reason for this is that the "b-th element and the a-th" difference "" is important, and the number itself can be anything.
For example, 2,3,3,4 has the same difference as 1,2,2,3, and 3,3,3,3 has the same difference as 1,1,1,1. As you can see, every sequence other than 1 starts has an equivalent sequence with 1 start.
You can do it all separately, but if you notice it, it may be a little easier to implement. By the way, the execution time will be halved, but it doesn't matter because it doesn't become TLE even if you search all the files including the beginning of 1.
Here are some similar issues. The top problem is just the right level of difficulty to get used to. The last two are a little more difficult D question level difficulty, but still easier than this question.
Tea level: ABC029 C --Brute-force Attack Green level: ABC161 D --Lunlun Number Green Level: Panasonic Programming Contest 2020 D --String Equivalence
Recommended Posts