XX...X.X.X.のような文字列で、$K$回まで.をXに置き換えてよい。連続するXの数の最大値を求める。
解法1
公式解説
書き換える場所の両端を尺取法で走査する。
書き換える区間の途中にある元々のXの数を累積和で保持しておく。
解法2
書き換える場所の両端を管理するのではなく、書き換え後の連続したXの両端を尺取法で走査する。
累積和を計算する必要がない。さっきやってみたが出来そうでまだ出来てない。
解法3
元の文字列
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|
X |
X |
. |
. |
. |
X |
. |
X |
. |
X |
. |
両端に.を追加する。追加しても結果は変わらない。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
. |
X |
X |
. |
. |
. |
X |
. |
X |
. |
X |
. |
. |
$ $.の場所を記録する。右から $i$ 番目の.の場所が $d_i$ になるようにする。
上の例だと、$d = [0,3,4,5,7,9,11,12]$。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
. |
X |
X |
. |
. |
. |
X |
. |
X |
. |
X |
. |
. |
| $d_0$ | $d_1$ | $d_2$ | $d_3$ | $d_4$ | $d_5$ | $d_6$ | $d_7$ |
$ $こうすると、.からXに変える場所の左端が $d_l$ のとき、右端は $d_{l+k-1}$ になる。
これが便利なのは、書き換え後のXの両端が $O(1)$ で求まること。
下は $(l,r)=(1,2)$ のとき。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
. |
X |
X |
X |
X |
. |
X |
. |
X |
. |
X |
. |
. |
| $d_0$ | $d_1$ | $d_2$ | $d_3$ | $d_4$ | $d_5$ | $d_6$ | $d_7$ | |||||
| → | 左 | 右 | ← |
$ $観察すると、書き換え後のXの左端は $d_{l-1}+1$ 、右端は $d_{l+k}-1$ 。
なので、$l$ を変えていって $(d_{l+k}-1) - (d_{l-1}+1) + 1$ の最大値をとればよい。
ただし、元の.の数が$K$より少ない場合を分ける必要がある。
本番中はこれで通した。
use proconio::{input, marker::Chars};
fn main() {
// 入力
input!{
s: Chars,
k: usize,
}
// '.'の場所を記録する。両端を`.`で囲んでおく。
let mut d = vec![];
d.push(0);
for i in 0..s.len() {
if s[i] == '.' { d.push(i+1); }
}
d.push(s.len()+1);
let mut ans = 0;
if d.len()-2 <= k { // 全ての`.`が`X`に書き換えられる場合
ans = s.len();
} else {
for l in 1.. {
if !(l+k < d.len()) { break; }
ans = ans.max( (d[l+k]-1) - (d[l-1]+1) + 1 );
}
}
// 出力
println!("{}", ans);
}
Take Home Message
$ $１個ずつカウントする($1+1+1\dots$)のは時間がかかるので、 $f(r)-f(l)$ に変換できないか考える。