競プロがんばりたい

Handstand

ABC124-D "Handstand"

(解説見ちゃった)

提出コード

考察

愚直に( $O(N ^2)$ 解法)

左端を固定( $0 \leq i \leq N-1$ )して， $i$ 番目以降の $0$ のまとまりを順に $K$ 回だけ $1$ に変換していきます．

その中で，連続する $1$ の数の最大値を更新していけばOK．

例えば，サンプル $2$ を取り上げます．

11101010110011

・ $i=0$ のとき

11101010110011

$2$ 回まで操作が許されているので， $0$ のまとまりを $i=0$ 番目以降の左から順に $1$ にします．

操作前：11101010110011

操作後：11111110110011

・ $i=7$ のとき

11101010110011

$2$ 回まで操作が許されているので， $0$ のまとまりを $i=7$ 番目以降の左から順に $1$ にします．

操作前：11101010110011

操作後：11101011111111

これを $i$ を $0$ から $13$ まで動かして $1$ の連続する数の最大を取ることで答えは出ます．

でもこれは $O( N ^2 )$ なのでTLEします．

累積和っぽいやり方( $O(N)$ 解法)

$0, 1$ が切り替わる場所をborder[ ]に記録してみます．

border[ ] $= \{0, 3, 4, 5, 6, 7, 8, 10, 12 \}$

これを前計算しておいて，あとは左端( $i$ 番目)を順に見ていき， $i$ 番目以降の $0$ の塊を $K$ 回だけ $1$ にしていきます．

実は左端は全探索する必要はないです．

なぜなら，例えばサンプル $2$ では $i=2$ より $i=0$ の方が明らかに左端として最適だからです．

つまり，連続する $0$ または $1$ のうち左端のみを全部見ていけばOKです．

左端が $1$ か $0$ かで状況は違います．

・左端が $1$ のとき．

下の図 $1$ のうち，上の段は入力列，下の段は入力列に対応するborder[ ]の中身が入っています．

そして，左端が $i=0$ の状況を考えてみます．

f:id:chankilu23:20201229123307j:plain

ここでは， $K=2$ 回まで操作を行えるので， $0$ の塊の位置を $2$ 回分飛ばすと見なして青矢印の終点位置にたどり着きます．

(累積和の性質上，たどり着く位置を一つ右にずらしています．)

$0$ の塊を $1$ 回飛ばすと $0, 1$ は $2$ 回変化します．

よって，サンプル $2$ では $K=2$ 回飛ばせるので，最終位置は初期位置から $2 \times 2 + 1 = 5$ だけ右にずれることがわかります．

ここで，この青矢印の始点と終点の位置でborder [ ]を使ってあげると，

border[ $0+5$ ] - border [ $0$ ] $= 7-0 = 7$

個の連続した $1$ を並べることが可能です．

ただし，右にずれた結果が入力長からはみ出した場合は，border [ ]の値は $N$ とします．

イメージでは， $N$ 番目以降で連続した $1$ を最大で $N$ 個並べられるということです．

・左端が $0$ のとき

左端が $1$ のときは，左端から $2 \times 2 + 1$ だけ右にずれることができましたが，左端が $0$ のときは $2 \times 2$ だけです．

右にずれた結果が入力長からはみ出すので，計算は

$14 -$ border [ $5$ ] $= 14 -7 = 7$

です．(下図 $2$ )

f:id:chankilu23:20201229125833j:plain

これらを一般化します．

まずはborder [ ] を作り，入力列を左端から順に見ていきます．

$i$ 番目が $1$ ならば，border [ $i + 2 \times K + 1$ ] $-$ border [ $i$ ]を計算．

$i$ 番目が $0$ ならば，border [ $i + 2 \times K$ ] $-$ border [ $i$ ]を計算．

ただし，上でも触れたように，右にずれた結果が入力長からはみ出した場合は，border [ ]の値は $N$ とします

これの最大値を順次更新していけばOKです．

感想

累積和の応用ってかんじですね．

累積和は基本的な問題しか解いたことなかったので，こういう使い方があるんやーって勉強になりました．

類題は解けるようになりたい...

そろそろ卒論に拍車をかけないといけないので競プロの精進は一気に落ちそうです．

恐らく年内にもう1問できたらいいなーぐらいで，1月は2問できるかできないかという予想です．

ワンチャン，良いお年を．