ABC135

This time, problem E was quite difficult. It felt harder than problem F. After listening to the explanation broadcast on Youtube, I finally understood. This is a memo for myself, so the Japanese is rough…

ABC #135 D - Digits Parade

Let dp[i][j] be the number of cases where the remainder is j when looking up to the i-th digit.

ABC #135 E - Golf

Prepare X>=0,Y>=0 in advance

1) X+Y is odd AND K is even

Return -1. No way to reach an odd address

2) X+Y>K

Let n=ceil(X+Y/K), and if X+Y and nK have different parity, do n++. Create a redundant path for the surplus nK-X-Y. Here, if X=0, the Manhattan distance is not correct in the initial movement, so do swap(X,Y) (of course, revert when outputting).

           +(X,Y)
           | Y
(0,0)+     -
   t |     | t = (nK-X-Y)/2
     |-----|
        X

3)X+Y<K

3-1) X+Y is even

n=2. The subsequent calculation is the same as 2).

           +(X,Y)
           | Y
(0,0)+     -
   t |     | t = (2K-X-Y)/2
     |-----|
        X

3-2) X+Y is odd (K is also odd from condition 1)

n=3. Can’t think of this. Only in this case, you need to take redundant paths in both X, Y directions.

                      p
                    +----+
                  (X,Y)  | Y
         (0,0)+          -
            t |          | t = K-X
              |-----|----|
                X     p = (K+X-Y)/2

4) X+Y==K

Can reach in one shot.

ABC #135 F - Strings of Eternity

Prepare rolling hash to enable string comparison in O(1). Other algorithms would also work. Make S sufficiently large in advance. Prepare UnionFind, When the i-th position of S matches T, and the i+T.size() position of S also matches T, Perform Union processing on i and i+T.size(). The maximum number of elements in a group across the entire UnionFind is the answer.