ABC #139 D - ModSum

If we set $p_1=N, p_2=1, p_3=2, … , p_N=N-1$, then $m_1=0, m_2=1, m_3=2, … , m_N=N-1$. So the answer is the sum of $1, 2, 3, …, N-1$.

ABC #139 E - League

Represent the match between $i$ and $j$ as vertex $(i,j)$. However, treat the reversed one as the same. Each vertex has the number of matches that should be done before $prev_{(i,j)}$ and a list of next possible matches $next_{(i,j)}$. Then, whenever we find a match with $prev_{(i,j)} = 0$, we simulate greedily playing that match. Note that each time we play a match, we decrement $prev_{(p,q)}$ of the next vertex.

ABC #139 F - Engines

Sort each vector by argument in advance, and connect the vectors so they span 720 degrees (this makes things easier later). Then we can see that the answer to this problem is the sum of consecutive vectors. Perform the following operation for all vectors:

  • Starting from a certain vector, add consecutive vectors and find the one with the longest length.

ABC #140 D - Face Produces Unhappiness

First, focus on unhappy people and how much we can reduce them. For example, if we extract unhappy people from $RLLLLRRRRRLLRRLLRRR$, we get $RL…….RL..RL…R$. Since consecutive people can be operated on simultaneously, we can consider it as $RLRLRLR$. Then we can repeat operations like $RLRLRLR$ -> $RLRLR$ -> $RLR$ -> $RR$ -> (empty).

ABC #140 E - Second Sum

Look from N to 1 in order. When looking at element $i$, elements $i+1, i+2, … , N$ are placed on the left and right. Calculate the combinations for cases where the maximum value is on the right and on the left, and sum them. I found the position of the maximum value using lower_bound of set.

ABC #140 F - Many Slimes

Greedily create slimes with the highest health first. Hmm, this time I felt problem D was harder than problems E and F…

ABC #141 D - Powerful Discount Tickets

Put all items in a priority queue q. Take them out in order for the number of discount tickets and perform the following operation:

  • Take out the item with the highest price from q.
  • Halve the price of that item (round down) and put it back into q.

ABC #141 E - Who Says a Pun?

Binary search on length len. For a certain length, use rolling hash to store hash values of all substrings in a map etc. If hash values match and there’s no overlap, we know that the condition is satisfied for that length.

ABC #141 F - Xor Sum 3

Consider each bit separately. First, calculate $A_1 \oplus A_2 \oplus … \oplus A_N$, and for bits where 1 is set, they don’t affect the answer no matter how you color them, so extract them. As a result, we get $A_1 \oplus A_2 \oplus … \oplus A_N = 0$. Here, let the XOR of blue be $X$ and the XOR of red be $Y$. Since $X \oplus Y = 0$, by the property of XOR, $X = Y$. So we want to find a way to select some from $A_i$ and maximize their XOR. Using the elimination method (like solving simultaneous linear equations), look from the upper bits, treat elements with 1 set as pivot rows, and XOR with other elements. As a result, we get $X = Y = A_1 \oplus A_2 \oplus … A_N$.