I solved all CD problems of Atcoder Beginner Contest #116 ~ #129. Also, for #126 ~ #129, EF problems were added, so I solved all of them. For F problems, I referred to explanation PDFs, explanation YouTube videos, and explanation blogs.

ABC #126 F - XOR Matching

https://atcoder.jp/contests/abc126/submissions/5909511

When M=3, a sequence of length 2^(M+1) has elements like {0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7}. In this case, set it as {<0,1,...,7 excluding K in ascending order> K <7,6,...,0 excluding K in descending order> K}.

  • For elements other than K: Only K remains between them, satisfying the condition
  • For K: <7,6,...,0 excluding K in descending order> remains between them. XOR gives K, satisfying the condition.

ABC #127 F - Absolute Minima

https://atcoder.jp/contests/abc127/submissions/5930963

Use the property that the median becomes the minimum value. When there are two medians, adopt the left one. It’s convenient to manage the median using priority queues for the smaller half and larger half separately. In the explanation video, they used the technique of inserting the same a twice and exchanging between queues, but the naive method of inserting only once also works fine. You need to organize so the queues don’t become unbalanced. For an update query, if a is included in the interval where the minimum value is taken, there’s no update to the minimum value. On the other hand, if not included, add the difference with the nearest point in the interval where the minimum value is taken to the minimum value.

ABC #128 F - Frog Jump

https://atcoder.jp/contests/abc128/submissions/5921198

Instead of handling A and B directly, consider with variables C=A-B and k=how many times backtracking occurs. When C is fixed, as k increases, more lotus leaves can be stepped on. Whether the same lotus leaf is passed twice or more is simply managed with a set.

ABC #129 F - Takahashi’s Basics in Education and Learning

https://atcoder.jp/contests/abc129/submissions/5945816

It was difficult. First, divide according to how many digits each element of the arithmetic sequence has. For example, if A=3, B=4, divide into 3,7 and 11,15,19 to consider. After division, you need to find sum_i=0^(l-1) (A+Bi)*10^k^(l-i-1). Divide into A sum_i=0^(l-1) 10^k^i and B sum_i=0^(l-1) i*10^k^(l-i-1) and calculate. Both are converted to recurrence relations and solved (corresponding to f,g in the code). I recommend watching the explanation video.

Atcoder Problems User Page