[PYTHON] Competitive professional devotion record 1-3 days (10 / 14,15,17)
I will post an article for recording the review of Arimoto (focusing on the problem of Mr. Kenchon's article) and AtCoder's devotion. I want to do my best for at least a month. Also, I'll just link the code, as it can put a lot of problems in one article.
First day
Ant book devotion
I also solved JOI's darts, AGC033-A, but I will omit it this time because it is easy.
ARC037B --Baum test
** $ N $ Concatenated graph without a vertex cycle $ \ Leftrightarrow $$ N $ Vertex Tree $ \ leftrightarrow $$ N $ Graph with $ N-1 $ edges connected by vertices **
I sometimes forget the above paraphrase, so I will keep it in my heart.
In this problem, all you have to do is count the connected components that form a tree, and you just need to decompose them into connected components with Union Find and find out how many edges are included in each.
Submission → link
AtCoder devotion
diff:1831
Result: AC? In total about 1.5 hours (I don't know the exact time because I don't touch the computer for a long time)
Consideration
I want to minimize the dictionary order, so first I will think about the ** optimal way to reduce mountains **. Initially $ i \ in [0, n-1] $ is the largest peak and the smallest index $ k $ element. By gradually reducing this peak, ** find the smallest index with the next largest peak **. Then, $ i \ in [0, k-1] $ becomes the element of the largest peak and the smallest index $ l $. This is ** recursively repeated **, so by finding the cumulative maximum (indexed), you can find out which mountain will be the largest in the middle with $ O (n) $.
The above discussion has given us how to move the maximum index, but we need to find ** how many times each index appears **. At this time, consider the figure below (the red circle is the location of the index that you move through).
In other words, the number of times the index of one mountain $ i $ appears is (the total height of each mountain reduced to the height of the next mountain $ j $), so (the number of mountains greater than or equal to mountain $ i $) $ \ times. $ (Height of mountain $ i $-Height of mountain $ j $) + $ \ sum_ {k} $ {(Height of mountain $ k $ lower than mountain $ i $ and higher than mountain $ j $)-( Mountain $ j $ height)} is the answer. This can be thought of as $ O (n) $ by ** arranging the mountains in ascending order and saving the number of mountains with a height of $ i $ or more **.
Therefore, the answer is to record the number of times in the array that stores the number of times each index appears and finally output them together. Also, the bottleneck is sorting, and the total amount of calculation is $ O (n \ log {n}) $.
Submit → link
the 2nd day
AtCoder devotion
diff:1740
Result: AC in about 20 minutes (but Esper)
Consideration
I solved it by intuition, but it seems that the answer was correct. However, I tend to hit with BIT recently, so I would like to be able to solve it with the $ O (N) $ solution.
I noticed that ** the operation is reversible ** (✳︎). Also, since it is reversible and can be unified only to $ A $ or $ B $, we decided to ** unify any character to $ B $ ** here. Then any string can be transformed into one of (empty string, $ B, BB $). You also need to prove that you can convert between ** (empty string, $ B, BB $) **, which is [editorial](https://img.atcoder.jp/arc071/editorial. It cannot be transformed as shown in pdf).
Also, if it is unified to $ B $, which of (empty string, $ B, BB $) will be determined by the remainder of dividing the length of the character string by 3. That is, ** $ (xs \ times 2 + xt), where the number of $ A and B $ in the selected partial continuous character string of $ S and T $ is $ (xs, ys) and (xt, yt) $, respectively. If % 2 = (ys \ times 2 + yt) % 2 $ holds, the same string ** can be created. Therefore, if the cumulative sum ** is taken from the number of ** $ A, B $, the number of $ A, B $ in a certain interval can be calculated by $ O (1) $. Therefore, it can answer up to $ 10 ^ 5 $ queries at high speed.
During the contest, I set $ 1 for $ A $ in each index and 0 for $ B $. ** Save the information of $ S and T $ in BIT **, and when a query comes, the sum is $ A $. I was looking for the number of, but the cumulative sum is easier and faster to implement.
(✳︎)… I managed to do something during the contest, but I wanted to solve it after proving it properly.
Submission → link
diff:1831
Result: AC in about an hour (spitting a lot of pena)
Consideration
It was a problem that I was not very good at because it was on a two-dimensional coordinate system, but I solved it. I would like to take this opportunity to dispel my weaknesses.
First, ** draw a diagram ** and think about it ** the time to be exposed to cosmic rays between two circles is the minimum ** when moving on a line segment connecting the centers * *is. In other words, the time to be exposed to cosmic rays when moving between two circles is max (0, (distance between centers of two circles)-(sum of radii of two circles)). ** If the circles overlap or are included, it will be 0 **, so even if you move between the two circles, you will not be exposed to cosmic rays.
In other words, the minimum time to be exposed to cosmic rays between any two circles can be found. Also, the start point and end point can be regarded as a circle with a radius of 0. Therefore, by considering the minimum time of exposure to cosmic rays as the distance, it is sufficient to solve the shortest distance problem ** from the start point to the end point in the graph of ** $ N + 2 $ vertices. Also, since the distance is non-negative, it can be solved using Dijkstra's algorithm, and the amount of calculation is $ O (N \ log {N}) $.
And ** because the distance is a decimal, make it double **, so there are the following points to be careful.
(1) Since double is typedefed as ll, be careful of ** type specification for integers **.
(2) To minimize the update of the distance between decimal numbers, ** add a value slightly smaller than the tolerance ($ 10 ^ {-11} $ in this case) to the larger one and make a judgment **.
(3) Specify to output in $ 10 $ digits after the decimal point.
(✳︎) Don't forget the ** INF initialization ** in Dijkstra's algorithm.
We will implement the Dijkstra method while suppressing the above points to be aware of. I used the code from this article.
Submit → link
Third day
AtCoder devotion
diff:1987
Result: AC in about 40 minutes
Consideration
First, consider the case where the average is 0 or more ($ \ leftrightarrow $ sum is 0 or more) by ** subtracting any element by $ k $ ** under the condition that the average is $ k $ or more. * * You don't have to think about the number of elements **. Therefore, first set all the elements to $ -k $.
Also, since it is a continuous subsequence, I thought about DP at first, but it is difficult because I was asked how many. Here, if you look at the ** continuous subsequence as an interval **, you can reduce it to the ** problem of considering the difference of the cumulative sum **. In other words, by setting $ S [i]: = i + 1 sum up to the $ th element ($ S [i] =-k $ when $ i = 0 $), a certain interval $ [l, r ] The condition that the sum of $ is 0 or more is $ S [r]-S [l-1] \ geqq 0 \ leftrightarrow S [r] \ geqq S [l-1] $.
In the case of the problem of the pattern of $ S [r] = S [l-1] $, it is managed using map, but this time it is implemented by BIT with the image of calculating the number of inversions **. In other words, if you record the number of $ S [i] $ in BIT in order from the largest $ i $ (✳︎), in a certain $ i $, the number of each value of the element with a larger index is already noted. It will be done. Therefore, since the condition ** $ r> l-1 $ is satisfied **, the number of values that are $ S [i] $ or more can be calculated by BIT in logarithmic hours.
Also, the value of $ S [i] $ needs to be large or negative, so ** coordinate compression ** (reference) ) And number $ 1 → x $. Also, $ x $ can only be $ n + 1 $ at most.
(✳︎)… It is easier to implement from the smaller one, but since it is not the essence, explanations etc. are omitted.
Submission → link
Recommended Posts