7K12 blog

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

ABC140 D - Face Produces Unhappiness

f:id:tkr987:20200728225306p:plain

https://atcoder.jp/contests/abc140/submissions/15507196

https://atcoder.jp/contests/abc140/submissions/9416948

  • 任意区間に対して人の位置を反転させた上で向きも反転させる
  • 反転したとき「連続文字列をグループ化した個数」と「幸福度」の増減に着目する
  • 連続文字列→ランレングス圧縮という気持ち

f:id:tkr987:20200728225605p:plain

連続文字列が幸福度になるので、ランレングス圧縮したい気持ちになる。境界を適当に選んだ区間を反転させると、区間内の幸福度は不変だが、境界の幸福度が+2増加し、連続文字列をグループ化した個数が-2減少すると分かる。したがって、グループが1個になるかK回のどちらかを満たすまで反転を繰り返し、幸福度を+2ずつ増やせばO(N)で答えが得られる。ただし、グループが2個になったときは幸福度が+1しか増えないので注意。なお、O(N)で処理するところO(1)で出力することも出来るが、バグりやすいのでO(N)が無難かもしれない(ぇ