モノグサプログラミングコンテスト2022 (AtCoder Beginner Contest 249) E - RLE (500)
連続する長さによって圧縮した後の文字列長は以下のように変わる
1文字の場合、2文字になるので1文字増加
2文字の場合、変わらない
3文字以上の場合、減少するが減少幅は桁数によって異なる
愚直に実装すると$ i文字目まで見て今の文字が$ j個連続していて文字列長または変化が$ kの個数を持つ必要がありこれは$ \mathcal{O}(N^3)になる
文字列の増加数は同じ文字の個数の桁数が同じ範囲では同じなのでまとめて考えられる
文字列長毎にセグ木を持っておく
事前に全ての位置でそこまで全て同じ文字だった場合の数を入れておく
文字種は26なので26が入る
2文字目以降で以下を行う
現在の文字列長毎に考える
1桁前の範囲からは2文字増加
2桁前の範囲からは3文字増加、というふうに現在の和に加算する
前回と違う文字は25種類あるので25倍したものを取り得る値とする
セグ木の操作は$ \mathcal{O}(\log N)なので全体で$ \mathcal{O}(N^2 \log N)
問題: https://atcoder.jp/contests/abc249/tasks/abc249_e
提出: https://atcoder.jp/contests/abc249/submissions/31209137
#モノグサプログラミングコンテスト2022 #ABC249 #500pt #E #モノグサプログラミングコンテスト #ABC #AtCoder
#ランレングス圧縮 #セグ木 #O(N^2\logN)