Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 297 C問題 PC on the Table

AtCoder ABC ABC297 C問題 300 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

${\tt T}, {\tt .}$ からなる長さ $W$ の $H$ 個の文字列 $S_1, \dots, S_H$ が与えられる.

以下の操作を何回か行う.

$1 \leq i \leq H, 1 \leq j \leq W-1, S_{i,j}=S_{i,j+1}={\tt T}$ であるような整数の組 $(i,j)$ を選び, $S_{i,j}, S_{i,j+1}$ をそれぞれ ${\tt P}, {\tt C}$ に置き換える.

最大回数行ったとき, 各文字列はどのようになっているか?

制約

$1 \leq H \leq 100$
$2 \leq W \leq 100$
$S_i$ は ${\tt T}, {\tt .}$ からなる文字列

解法

操作は各行ごと独立なので, $H=1$ の場合について考察すれば良い.

$S_1$ は ${\tt T}$ が連続して $a_1, a_2, \dots, a_k$ 文字続いているとする.

このとき, 操作回数の最大値を $K$ とする. まず, 操作対象の箇所は互いに交わらない連続する $2$ 文字を選ばなくてはならないので,

$\displaystyle K \leq \sum_{t=1}^k \left \lfloor \dfrac{a_t}{2} \right \rfloor$

である.

また, 各 $a_t$ 個の連続した ${\tt T}$ において, 左から順に ${\tt P}, {\tt C}$ に置き換えることより,

$\displaystyle K=\sum_{t=1}^k \left \lfloor \dfrac{a_t}{2} \right \rfloor$

であることがわかる.

よって, 最大値を達成する一例を作れたので, 上の方針を実装すればよい.