C - YY Square 解説 by evima
Assume that the contribution of the YY
s in \(\mathrm{str}(P)\) to the score are \(1, 3, 5, \ldots\) from left to right.
Indeed, if YY
occurs \(k\) times in \(\mathrm{str}(P)\), the score is \(k^2\), and we have:
\[1 + 3 + 5 + \cdots + (2k - 1) = \sum_{i = 1}^k (2i - 1) = k^2.\]
If, for every pair of adjacent Y
s in the grid, we can compute its total contribution over all possible paths, the answer is the sum of those values.
Assume that both \((i, j)\) and \((i + 1, j)\) have Y
written on them, where \(1 \le i < H,\ 1 \le j \le W\).
Then, the total contribution of this YY
is \(a + 2b\), where:
- \(a\) is the number of paths containing the move \((i, j) \to (i + 1, j)\), and
- \(b\) is the total number of times those paths move between adjacent
Y
squares before reaching \((i, j)\).
Here, we have:
\[a = \binom{i+j-2}{i-1} \times \binom{H+W-i-j-1}{H-i-1}.\]
Let \(\mathrm{dp}(i, j)\) be the total number of times the paths move between adjacent Y
squares before reaching \((i, j)\). After computing these by naive dynamic programming (DP), we can compute:
\[b = \mathrm{dp}(i, j) \times \binom{H+W-i-j-1}{H-i-1}.\]
Computing $\mathrm{dp}(i, j)$
Let $\mathrm{dp}(1, 1) = 0$. We will do a naive "receiving" DP from left and up, and if there is aYY
on the way, add the following extra value.
If $1 < i \le H,\ 1 \le j \le W,$ and $S_{i-1, j} = S_{i, j} = {}$Y
, there are paths to $(i, j)$ via the move $(i-1, j) \to (i, j)$, the number of which is equal to that of the paths to $(i-1, j)$. Considering this, we add $\displaystyle\binom{i+j-3}{i-2}$ to $\mathrm{dp}(i, j)$.
If $1 \le i \le H,\ 1 < j \le W,$ and $S_{i, j-1} = S_{i, j} = {}$Y
, there are paths to $(i, j)$ via the move $(i, j-1) \to (i, j)$, the number of which is equal to that of the paths to $(i, j-1)$. Considering this, we add $\displaystyle\binom{i+j-3}{i-1}$ to $\mathrm{dp}(i, j)$.
We can similarly process a horizontal pair of \((i, j)\) and \((i, j + 1)\), both of which have Y
written on them, where \(1 \le i \le H,\ 1 \le j < W\).
The DP in the pre-computation and the computation of the total contribution both take \(\mathrm{O}(HW)\) time, which is the complexity of this solution.
投稿日時:
最終更新: