[PYTHON] Competitive professional devotion record Day 4-6 (10 / 18,22,23)
It is a continuation of the devotion record. I was so late that I couldn't review some of the issues. After all, due to my personality, I should review it immediately ...
Day 4
AtCoder devotion
ARC079E - Decrease (Judge ver.)
diff:1791
Result: about 30 minutes
Consideration
I'm surprised that the solution I decided to put out for the time being passed. (Although there was an intuition that it would decrease exponentially **.)
Repeat subtracting $ N $ from the maximum value and incrementing the others by 1. Now suppose you have selected ** $ a \ _i $ only $ b \ _i $ times **. At this time, if the total number of selections is $ s $, then $ [\ frac {a \ _i + (s-b \ _i)} {N}] = b \ _i $ holds. I thought about transforming this formula and solving it analytically.
However, it is difficult as it is, so considering ** at least the required number of times **, you can operate at least $ [\ frac {a \ _ i} {N}] $ times for any $ a \ _i $. I realized that I needed. I calculated this for any element and thought that it would be foolish to update $ a \ _i $, so I submitted it and AC. When I checked it, it seems that other people who solved it have not proved it, so I feel that there is no solution other than solving it with this intuition. It's a moody problem.
Submission → link
diff:1831
Result: AC in about 20 minutes (1WA with wrong output format)
Consideration
It's a construction problem, so I'll think about making it ** conveniently. I feel that the power around here was attached by Kodofo's bacha.
First, consider a subset that satisfies two conditions (concentration is $ k $). At this time, from condition 1, the number of ** other subsets is at most $ k $ **. Also, if there is a set ** whose cardinality is not $ k
Therefore, the cardinality of any set is $ k $. Furthermore, since the elements contained in the set of subsets have paired elements, the number of the subsets is $ k + 1 $. Therefore, from condition 1, the total number of elements included in the subset set is $ 2n $, so it is necessary to satisfy ** $ k (k + 1) = 2n $ **.
$ K $ that satisfies $ k (k + 1) = 2n $ checks all divisors of $ 2n $. And, if you think about the construction method, thinking that ** it always holds when this condition is met **, the condition is satisfied in the following cases. If you experiment ** while paying attention to symmetry, you will think of it.
In other words, you can decide by starting from the diagonal component (like) and then extending in order. Also, whether the above always satisfies the construction condition can be shown by considering the common numbers between 1 and 2 to 4, between 2 and 3 to 4, and between 3 and 4 in order. .. Therefore, this can be easily obtained by simply implementing the fact that the diagonal components are extended in order. It's a bit cumbersome to implement, but see the submission link below for more details.
(✳︎)… This area can be understood by intuition when considering symmetry, but if it is verbalized to some extent, there may be less anxiety.
Submission → link
Day 5
AtCoder devotion
diff:1896
Result: AC in about 20 minutes
Consideration
** I'm glad I solved it while maintaining sufficient validity **.
Repeat the operation to make $ A = B $. Tozan will reduce $ A $, Gezan will reduce $ B $, the former aims to maximize the number of operations, and the latter aims to minimize it. (However, the answer is 0 when $ A \ _i = B \ _i $ from the beginning.)
Here, it is important that ** the total of $ A and B $ does not change when both operations are completed ** (✳︎). That is, for $ A \ neq B $, there is at least one different $ i $, which is $ A \ _i > B \ _i $ and $ A \ _i \ <B \ _i $. Therefore, the ** optimal actions to be taken by both parties ** are as follows.
Tozan ... Reduce $ A \ _i $ which becomes $ A \ _i \ leqq B \ _i $ Gezan ... Reduce $ B \ _i $ which becomes $ A \ _i \ <B \ _i $
Also, since Tozan is the first player, you can reduce any $ A \ _i $ that becomes $ A \ _i \ leqq B \ _i $ to 0. ** Gezan should reduce $ B \ _i $ accordingly **. However, even if Tozan does this, Gezan cannot set any $ B \ _i $ for which $ A \ _i \ leqq B \ _i $ holds to 0 ($ \ because $ (✳︎)). Therefore, if $ A \ _i $ that holds $ A \ _i > B \ _i $ can be reduced to $ A \ _i \ leqq B \ _i $, $ A \ _i $ can be reduced to 0. $ B \ _i $ must also be 0. By repeating this, ** there is one set of $ A \ _i, B \ _i $ ** that remains, and from (✳︎), $ A \ _i = B \ _i $. Therefore, this can be the smallest $ B \ _i $ ** in which ** $ A \ _i > B \ _i $ holds, until only this $ A \ _i = B \ _i $ remains. The number of operations is the answer you want.
(Various proofs are omitted above, but it can be proved by taking advantage of the condition (✳︎).)
Submission → link
Day 6
AtCoder devotion
ARC098E - Range Minimum Queries
diff:1978
Result: 2WA in 45 minutes (I almost gave up, but I'm glad I got stuck)
Consideration
The easiest is ** to count $ q $ from the smallest **, but there are other cases where it can be the smallest. This corner case is easy to make.
Also, since the elements to be removed change depending on the order in which the continuous subsequence of length $ k $ is selected, ** it is difficult to focus on the operation and consider it , so I tried to fix either the minimum value or the maximum value. I thought ( The main customer fell paying attention to the elements! **). Furthermore, since the minimum values are removed in order, I thought about ** fixing the minimum values **.
Therefore, I wondered if the minimum value would be $ x $ or more. Also, under this element, continuous subsequences of length $ k $ containing elements less than $ x $ cannot be selected **, so if the index of elements less than $ x $ is $ i, j $, then $ 0 $ Consecutive subsequences of length $ k $ can only be selected within ~ $ i-1 $, $ i + 1 $ ~ $ j-1 $, $ j + 1 $ ~ $ n-1 $. Also, when there are more than $ q $ of continuous subsequences that can be selected, the elements to be removed by the operation may be $ q $ from the smallest of the selectable elements. At this time, the minimum value is $ x $. The maximum value above is minimized **.
Therefore, apply $ x $ in order from the smallest element contained in $ a $ (maximum $ N $), and divide ** $ a $ by elements equal to $ x $ ** to minimize the value. You just have to look for. In addition, the number of operations that can be performed decreases monotonically because the length of the continuous subsequence that can be selected is shortened by performing division. So if you can't do more than $ q $ operations, you don't have to think about $ x $ anymore and you break (the answer doesn't change if you don't break).
Submit → link
diff:1747
Result: 5WA over 1 hour (did different in consideration and implementation)
Consideration
Below, the discussion is 1-indexed, but the implementation is 0-indexed.
Despite finding a good way in the process of thinking ** the implementation was different and debugging was ruined **.
Since it is a construction problem, look for a convenient case. Also, as you can easily see (from the sample), $ s [n] = 0, s [n-1] = s [1] = 1 $ and $ s [i] = s [ni] for any $ i $. ] If it is necessary to satisfy $ and even one is not satisfied, -1 is output. Also, consider building to ** show that this is also sufficient **.
First of all, I was thinking about the graph when $ i = 1,2,3,… $ and $ s [i] = 1 $ in order, but it was a bad method without abstraction. Next, I thought that the vertices would be determined according to the information of $ s [i] $ in the ascending order of ** $ i $ **. Then, I found that it seems that a graph that satisfies the subject can be generated by doing the figure below. (Honestly, I feel that this is ** the only way to get it right **.)
In other words, ** if you want to verbalize the above figure ** (← it was not done while solving ...), assuming that the last 1 of $ S $ is ignored, ** side is preceded by each character Correspond from **, and when 1 comes, move to the next and branch while 0 comes. Also, if you ** save the branch source as $ now $ **, you only have to connect the vertex from $ now $ when connecting the next vertex. However, when ** 1 arrives, the branch source will change to the currently connected vertex **, so you need to remember to update it.
Submission → link
(Re) Submission → Link
Recommended Posts