B - Three Coins 解説 by rng58_admin
For a given sequence \(x_1, \cdots, x_k (x_1 < \cdots < x_k)\), let’s check if it’s possible to reach a state where these \(k\) cells contain coins, and no other cells contain coins.
First, notice that only the values of \(x_1 \mod 3, \cdots, x_k \mod 3\) are important. This is because, by doing the following operations,
...#
-> ####
-> #...
all states can be converted to the “minimal” state that preserves the values of indexes modulo \(3\).
Thus, we get the following problem:
- We start with an empty string. We are allowed to insert strings
012
,120
,201
in any position. Also, we are allowed to remove a substring from the string if the substring is one of012
,120
,201
. Is it possible to make a given srting?
We can prove that we never need to use the removal operation. If a removal operation comes right after an insertion operation,
- In case the two operations are performed on disjoint positions, we can swap the operations (and repeat swapping and moving the removal operation earlier while you can; you eventually have to stop at some point.)
- Otherwise, the two operations cancels out. For example,
01
->01201
->01
(inserted201
and removed012
, but nothing changed.)
To summarize, a sequence \(x_1, \cdots, x_k\) is valid if for some \(p, q, r (p < q < r)\),
- \(x_q = x_p + 1, x_r = x_p + 2 \pmod 3\)
- \(x_1, \cdots, x_{p-1}\) is a valid sequence.
- \(x_{p+1}, \cdots, x_{q-1}\) is a valid sequence.
- \(x_{q+1}, \cdots, x_{r-1}\) is a valid sequence.
- \(x_{r+1}, \cdots, x_{k}\) is a valid sequence.
Now it’s easy to get an \(O(N^3)\) DP to solve the problem.
投稿日時:
最終更新: