A - Rhythm Game

Hint 1

Try regarding each button press as a “task,” and rephrase the problem as a scheduling problem.

Hint 2

Suppose there were no release‑time constraints, that is, every button appeared at time $0$ and vanished at time $T[i] + D + 0.5$. Which order would be optimal?

Hint 3

In fact, without release‑time constraints it is optimal to process buttons (tasks) in non‑decreasing order of $T_i + X_i$. After rearranging them in that order, think about what form the optimal permutation of $1,2,\dots,N$ looks like with release‑time constraints.

Hint 4

Use the observation in Hint 3 and solve the problem with DP.

Editorial: https://atcoder.jp/contests/agc072/editorial/12777

B - AGC Language

Hint 1

Consider the case $K = 1$. If you draw the diagram obtained by interpreting A as $+1$ and C as $-1$, it is relatively easy to solve it in polynomial time (about difficulty 1200).

Hint 2

For $K = 1$, the number of $(l, r)$ pairs that must be examined can be reduced from $O(N^2)$ to $O(N)$.

Hint 3

For $K = 1$, you can actually narrow the candidates to $O(\sqrt N)$ possibilities for $l$ and $O(\sqrt N)$ possibilities for $r$.

Hint 4

Think about the optimal conditions on $l$. Using the same diagram (A as $+1$, C as $-1$), it is best if $l$ coincides with a point where the height changes. Besides those points, there is one more rule that lets you discard additional candidates—what is it?

Hint 5

Let the intervals separated by height $0$ form “connected components.” It suffices to consider, as $l$, only the position of maximum height within its component. Combining this with Hint 4 leaves only $O(\sqrt N)$ candidates.

Hint 6

Once you have solved the $K = 1$ case, fix how far $l$ is from the beginning and how far $r$ is from the end, and study how the swap count $f(k)$ changes with $k$.

Editorial: https://atcoder.jp/contests/agc072/editorial/12778

C - Human Exercise

Hint 1

For some small $N$ and $K$, try printing the number of times each cell is visited over the $K$ exercises. What property do you notice?

Hint 2

The pattern is symmetric about the anti‑diagonal line through $(1,N),\,(2,N\!-\!1),\dots,(N,1)$. Therefore, if you can solve the problem restricted to the upper‑left triangular half (the $\frac{1}{2} N(N+1)$ cells), you can solve the original one.

Hint 3

Look at which direction the walk takes each time it departs from $(1,1)$.

Hint 4

The answer to Hint 3 is: on odd visits it goes down, on even visits it goes right. Apply the same reasoning to other cells as well.

Hint 5

Use the observations from Hint 4 to build a DP solution.

Editorial: https://atcoder.jp/contests/agc072/editorial/12779

D - Magician

Hint 1

Regard `0` as an opening parenthesis and `1` as a closing parenthesis. No matter what sequence of $(a_i, b_i)$ appears, it is possible to ensure the final string is a valid parenthesis sequence.

Hint 2

Moreover, you can make the final string a valid parenthesis sequence even when reading its characters in any fixed order you choose, such as “3 → 7 → 1 → 8 → 4 → 5 → 6 → 2”.

Hint 3

For $N = 3$ or $N = 4$, experiment programmatically to find, for each announced letter, which reading order of the string should form a parenthesis sequence.

Hint 4

For $N = 4$,the following strategy passes; generalize its pattern to other values of $N$.

• If the host announces A, read the string in the order 2 3 4 5 6 7 8 1 and make it a parenthesis sequence.
• If B, read it 4 5 6 7 8 1 3 2.
• If C, read it 6 7 8 1 5 2 3 4.
• If D, read it 8 1 7 2 3 4 5 6.

Editorial: https://atcoder.jp/contests/agc072/editorial/12780

E - Flights 2

Hint 1

First, study the case of a **path graph**. As an example, let $N = 6$, $F = 10$, with edges $1 \to 2 \to 3 \to 4 \to 5 \to 6$, each of weight $1$. Consider two rate vectors: $R = (0,2,1,5,8,0)$ and $R = (0,9,5,3,8,0)$. What routes are optimal? They need initial cash $28.5$ and $23.75$, respectively.

Hint 2

Observe how you exchange miles for money in Hint 1’s solutions.

Hint 3

Based on Hint 2, determine under what circumstances an exchange neither leaves you with 0 miles nor occurs when your money is 0.

Hint 4

Such exchanges described in Hint 3 never occur twice in a row. Using this fact, solve by DP the decision version of the problem on a path graph where the initial cash is fixed.

Hint 5

Extend the method of Hint 4 to general graphs.

Hint 6

If your solution in Hint 5 resembles Bellman–Ford, try converting it to a Dijkstra‑style method.

Hint 7

Find a way to avoid binary‑searching on the initial cash.

Editorial: https://atcoder.jp/contests/agc072/editorial/12781