7K12 blog

猫でも分かるアルゴリズム解説

CPSCO2019 Session4 D - Boring Sequence

f:id:tkr987:20200627175204p:plain

https://atcoder.jp/contests/cpsco2019-s4/submissions/13597815

  • 退屈Tを固定すると書き換え回数changeが計算できる
  • 書き換え回数 change \le Kの条件で二分探索することで退屈Tが求まる

f:id:tkr987:20200627175745p:plain

退屈TをO(1)で考えるのは難しいので、退屈Tが許される範囲を二分探索で求める。退屈Tを固定すると(連続したN個の部分列に対して)書き換え回数はchange = N / (T+1)で簡単に計算できる。数列をランレングス圧縮で連続部分列に分解し、全ての連続部分列に対しての書き換え回数合計がK以下となる範囲を二分探索で求め、そのときの退屈Tが答えになる。計算量は  O(N \log N)