Atcoder

Submission Code How many moves are needed in the vertical and horizontal directions respectively. Vertical Direction Simply moving downward, so it takes $k$ moves. Horizontal Direction Let $a_x$ be the information about where you originally came from when you moved to cell $x$. In other words, you start from $a_x$ in the 1st row and move to $x$ in the $k$-th row. For each $k$, think of starting from one of the cells in the forbidden area and moving to $b_i+1$....

Submitted Code After watching the explanation broadcast, I understood the approach, but it took a while from there. I think this is a problem with relatively heavy implementation. Consider dividing the answer palindrome LR into string L and string R. Initialize both as empty strings. When adding $s_i$, add it to the right side of L or to the left side of R. Suppose after adding $s_i$ several times, we have L="abcde" and R="cba"....

Submission It was a red difficulty problem. Reading the problem statement made it seem approachable, but it wasn’t that simple. First, I considered an $O(N^3)$ DP, then approached it by reducing the computational complexity based on that. We look at $i = 2, 5, 8, 11, \dots$ at intervals of 3 characters. Let dp[i][x][y] be the maximum score when we’ve examined up to the $i$-th position and the previous two characters are $x$ and $y$....

Submitted Code Focus on the fact that in a tree, “number of connected components = number of vertices - number of edges”. Intuitively, it can be understood as: when vertices increase, the number of connected components increases by 1, and when edges increase, the number of connected components decreases by 1. $f(L, R)$ can also be found using this. $$ \begin{aligned} &f(L, R) \\ &= Number of points contained in interval [L \ R] \\ &- Number of edges with both endpoints in interval [L \ R] \\ \end{aligned} $$...

Submitted Code Failed on test case after_contest01.txt added after the contest. Since I passed everything else on my own, my consideration was insufficient. First, divide into cases (A) where the answer is negative and (B) where the answer is non-negative. For (A), greedily take in order of smallest absolute value. Let’s think about case (B). First, prepare two queues. Non-negative values sorted in descending order (e.g., 9 6 5 2 1 0 0) Negative values sorted in ascending order (e....

Submitted Code As prerequisite knowledge, it’s good to know that this is a game called Nim. Nim has a winning strategy: take XOR of the number of stones in all piles $A_i$, and if the result is anything other than 0, the person whose turn it is can always win with optimal moves. When your turn comes in a winning state with XOR != 0, by cleverly removing a certain number of stones from a certain pile, you can transition to a state with XOR = 0....

Submitted Code Looking at the explanations, it seems that if we think of inserting alphabets arbitrarily $K$ times and consider the positions of each character in $S$ as fixed in a string of length $N+K$, it works well. Thinking that way, we just need to consider how to insert $K$ characters in a string of length $N+K$. Let’s think using Example Input 1. S = “oof” N = len(“oof”) = 3 K = 5 For example, place ‘o’ at position 1, ‘o’ at position 3, and ‘f’ at position 5....

Submitted Code I think reflecting after solving is important. Find the shortest path from the start position to the goal position on a 2D plane. However, there are some blocks on the plane, and those cells cannot be passed through. Furthermore, in one move, you can advance an arbitrary number of cells from $1 … K$ in the same direction. Consider the graph with vertices as $(y, x, dir)$ and calculate the shortest path using Dijkstra’s algorithm....

I completed all problems in EDPC. This is a miscellaneous memo, not a cleanly organized solution guide. W - intervals Let $dp_i$ be the final score when some bits are set to 1 and the rightmost 1 is at position $i$. Here, $dp_i$ can be calculated as the sum of $ max_{j=0 … i-1} dp_j$ and the score obtained when setting the $i$-th character to 1. Let $block_i$ be the set of blocks whose right end $r$ is $i$....

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)}$....

I solved several ABC problems but forgot to record them in my blog. I’ll write them all together here. ABC #136 D - Gathering Children Once you enter an RL pair, you can’t escape. Move an even distance and attach to the RL pair. ABC #136 E - Max GCD Sort first, bring small values closer to 0, and bring large values closer to the answer $d$. Calculate the cumulative sum from both forward and backward directions....

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....

Continuation from last time. I solved AtCoder Beginner Contest #130 ~ #133, so I’m summarizing them. I still can’t solve them without explanations… ABC #130 F - Minimum Bounding Box Let dp[i][j] be the number of combinations when the i-th and j-th are partial common substrings. By memoizing the update formula, it can be calculated quickly. ABC #131 F - Must Be Rectangular! Consider the (x,y) coordinates as a bipartite graph....

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,....

I solved all CD problems from Atcoder Beginner Contest #1 to #115. I was able to solve about 70% of the C problems and about half of the D problems on my own. I rarely used special algorithms, and I think they can be solved if you can think through them properly. Here are some useful things to note: Try solving the first 1-2 examples by hand. Especially for geometry problems, actually draw them out....

I tried competitive programming for a bit. Codeforces #308 (Div.2) First time participating in Codeforces. In the end, I only solved A out of the 5 problems (A-E). Problem A was just implementation, so it didn’t take much time to solve. For problem B, I think it could have been solved by making a histogram, but I realized that too late. For problem C, I failed on the 4th pretest. I didn’t attempt D or E....