Kazun の競プロ記録

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

AtCoder Beginner Contest 229 D 問題 Longest X

AtCoder ABC ABC229 D問題 400 pts

問題

提出解答

問題の概要

$"{\tt .}", "{\tt X}"$ からなる文字列 $S$ が与えられる. 以下の操作を高々 $K$ 回行うことができる.

$S$ にある $"{\tt .}"$ を $"{\tt X}"$ に置き換える.

高々 $K$ 回の操作後, $"{\tt X}"$ は最大で何個連続させられるか?

制約

$1 \leq |S| \leq 2 \times 10^5$
$S$ は $"{\tt X}", "{\tt .}"$ からなる文字列
$0 \leq K \leq 2 \times 10^5$
$K$ は整数

解法

$1 \leq L \leq |S|$ に対して, 「答えが $L$ 以上になるか?」という問題を考える. この問題の解答は単調減少なので, 二分探索で最終的な答えを求めることができる.

よって, 「答えが $L$ 以上になるか?」ということを考える. つまり, ある連続する長さ $L$ の区間において, $K$ 回の操作で全て $"{\tt X}"$ にできるかどうかを判定することになる.

これは長さ $X$ の区間で, その区間にある $"{\tt .}"$ の個数が $K$ 個以下であることが可能な必要十分条件になる.

事前に累積和を利用して, $T_i$ を $T_1,\dots, T_i$ にある $"{\tt .}"$ の個数を計算することにより, $O(|S|)$ で判定できる.

よって, $O(|S| \log |S|)$ で正解を導くことができた.