I will resume the memo of devotion. I will summarize it in a more fragile way than usual articles, and I will review it as soon as I solve it.
diff:1911 Result: AC for a total of about 2 hours
Submission: https://atcoder.jp/contests/agc014/submissions/18039440
First of all, move → open → move →…, so if there is a room that is not vacant yet, you will not be able to proceed to that room, which is a problem. Therefore, I thought that it would be better to manage ** the number of movements and the minimum number of vacant rooms , but this is not countable and it seems that it will take a lot of calculation. Here, if it is a pattern of open → move → open →… ( think about dropping it in a simple case! **), you can see that you only have to select the room at the nearest end ($ \ because $ that room). Because you can open all the closed rooms until you get to).
Therefore, it can be seen that it is only necessary to consider ** separating only the first movement **. In other words, since you can only trace the rooms that are not open in the first move, consider BFS ** that traces only the rooms that are open and the depth is less than $ k $. Then, in the pattern of open → move → open →… after that, it is only necessary to find the shortest path from the room that can be traced by BFS to the end room (four directions), and ceil (the length of the shortest path). / k) +1 is the answer. Therefore, the minimum value in the room that meets the conditions is the answer.
It wasn't bad to think that it would be good to have two pieces of information, ** the number of movements and the minimum number of vacant rooms **, but it took time to reach the idea of ** devising the operation method **. It wasn't good to go too far. I want to keep in mind the attitude of looking at problems from multiple angles, which seems to indicate that the amount of problems to be solved is small.
diff:2803 Result: AC in 30 minutes for discussion + implementation, 50 minutes for bug fix Submission: https://atcoder.jp/contests/agc012/submissions/18040503
** Focus on balls of the same color $ c $ **, the combination of the two balls must be less than $ x $. At this time, by ** selecting one of the two balls with the color $ c $ and the ball with the smallest weight **, the other ball can be made as heavy as possible. In addition, all arrangements can be realized between balls weighing less than $ x $ together with the smallest ball of color $ c $ ($ \ because $ ** minimum weight ball). You should always select **). … ①
Similarly, if you also note ** different balls **, you can select the ball with the smallest weight ** (color is $ c $) as one of the balls of all colors. You can have the same argument as. However, as the other ball, you can only select a ball whose color is other than $ c $ **. Therefore, it can be seen that for a ball with a color of $ c
From the above, by ** considering a disjoint set system of balls whose positions can be exchanged **, the positions can be exchanged between any elements within the disjoint set. Therefore, it is sufficient to divide the operation in the order of ① and ② and perform unite in the Union Find tree. Also, when there is a disjoint set system, the arrangement of balls in a disjoint set of size $ l $ is $ l! $. Also, since you want to find the sequence of ball colors **, you need to ** divide the balls of overlapping colors by the degree of overlap **. Here, the multiplicity is defined as $ l ^ {'}! $ If the number of balls of a certain color $ c ^ {'} $ is $ l ^ {'} $.
To implement the above, the following data structure etc. should be prepared.
colors[i]:=Index i ball color
color[i]:=Of the ball that becomes color i(weight,index)An ordered set that stores
weight:=(weight,index)An ordered set that stores
In (1), you should look at $ color [i] $ in order and look at the balls that can be combined with the minimum weight in order from the ball with the smallest weight. In (2), look at $ weight $ in order, and look at the balls that are different from the smallest ball color $ c $ in the same way as in (1), and then look at the balls that become $ c $ in the same way as in (1). Just take a look. See the submitted code for details.
The discussion worked, but I didn't realize that ** I was doing something different between the discussion and the implementation **. It's a pattern that's easy to get hooked on, so I want to be especially aware of it when fixing bugs.
Tenka1 Programmer Contest 2017 D - IntegerotS
diff:1794 Result: 20 minutes for consideration, 15 minutes for basic implementation, 15 minutes for bug fixing Submission: https://atcoder.jp/contests/tenka1-2017/submissions/18043771
First, when selecting a certain $ A \ _i $, selecting $ A \ _j (= A \ _i) $ does not affect bitwise or, so the given information will be the same value $ A \ _i $ By putting them together, $ A \ _i $ can have different values. Looking at the conditions of the problem statement under this, it seems that it can be solved with an idea close to the digit DP because there are conditions of ** $ k $ or less. Also, I noticed that I couldn't select an element with $ MSB $ larger than $ MSB $ ($ m $) of $ k $, so I decided to ** classify by $ MSB $ of each value **. .. At this time, you cannot choose $ MSB $ that is larger than $ m $. Also, if you select only the elements that have $ MSB $ that is smaller than $ m $, you know that bitwise or is smaller than $ k $ at this point, so you can select such elements. However, if I have $ msb $ which is the same as $ m $, I realized that the digits below ** $ msb $ should be less than $ k $ **, so ** the digits DP * in order from the upper digit. I decided to take a policy close to *. In other words, the set of numbers that can be selected when looking at a certain digit is $ s $, and is as follows. (By the way, it is easier and faster to implement by managing whether $ s $ is selected or not with a bool array)
When the $ i $ bit is seen, the following processing is performed and then the $ i-1 $ bit is processed.
(1) When that bit of $ k $ is set It is one of the solution candidates because bitwise or becomes smaller than $ k $ by selecting only the number of those included in $ s $ whose bits do not stand.
(2) When that bit of $ k $ is not set If you choose a number with that bit set, bitwise or will be larger than $ k $, so ** such numbers are excluded from $ s $ **, and bitwise or is not always smaller than $ k $. There are no candidates for a solution.
The maximum value among the solution candidates obtained by performing the above with arbitrary bits may be obtained. Also, in the above, only the processing of less than $ k $ is performed, and the processing of (1) and (2) when ** $ i = 0 $ can be performed as the processing of $ k $ or less **, so (1) In the case of, any element contained in $ s $ can be selected, and in the case of (2), any number contained in $ s $ whose bit does not stand can be selected. And since there is no msb of ** $ k = 0 $ **, at this time, the value of the 0 element included in $ s $ should be output in the initial state.
(✳︎)… The point to be aware of in the digit DP (problem close to) is that ** it should be below a certain digit **. However, in the following cases ** Be careful only when the values are equal **.
I knew the type of corner case I had seen so far, but I stepped on it. ** I want to make the part that seems to be a corner case stand out when considering **.
diff:1404 Result: 10 minutes for consideration, 10 minutes for basic implementation, ∞ minutes for bug removal → Check and confirm that there is a solution, then remove the bug and AC Submission: https://atcoder.jp/contests/agc020/submissions/18056229
(Hereafter, $ k $ in the question text has been replaced with $ n $, but don't worry.)
First, $ a [n-1] $ must be 2. At this time, I wonder which of the minimum and maximum values is easier to find. At this time, the construction of the minimum value should be made as small as possible so that it is a multiple of ** $ a [i] $ at the end of each round **, so I can think of it immediately. In other words, when $ check [i] $: = (the number of children remaining after the round $ i $ is over), $ check [i] = \ lceil \ frac {check [i + 1]} {a [ i]} \ rceil \ times a [i] $ is the minimum (it doesn't always hold as you can see in sample 2).
Also, to maximize the result based on the minimum, the maximum is ** $ check [i + 1] + a [i] -1 $ or less for $ check [i] $. It should be the number of $ a [i] $ **, so $ check [i] = \ lfloor \ frac {check [i + 1] + a [i + 1] -1} {a [i]} \ rfloor \ times a [i] $ is the answer.
Actually, if it holds at the minimum value, it also holds at the maximum value, so it should have been divided into ** stages as the construction at the minimum value → the judgment of whether the constructed product is correct → the construction of the maximum value **. I made a bug because I did the construction and judgment at the minimum time at the same time. ** I want to keep in mind that I will design a program that will not cause bugs even if the amount of writing increases.
In addition, it was swamped ..., I made a bug by doing the construction and the judgment of the corner case at the same time.
Recommended Posts