ABC140_D(Face Produces Unhappiness)

問題

• AtCoder Beginner Contest 140- D

考えたこと

• 最初は左端から入れ替える、入れ替えないみたいな操作をすることを考えた
  • 手計算でも計算量が多くなりすぎるので無理と判断
  • 何かしらのロジックで一気に解けそうとは思ったがそれ以上進まず
• 残念ながらわからなかったので解説を見る

解説を見ての気づき

• 前提として全員が同じ向きを向いた場合に、幸せな人は n - 1 人となる
• 今現在の幸せ度は n - 1 - 幸せではない人の数
• 一回の反転で幸せにできる人の数は最大でも2人

上記をもとにした計算式

• n - 1 - (幸せではない人の数 - 2 * 反転できる回数) が 最大の幸せ度
  • ただし n - 1 が最大なので (不幸な人の数 - 2 * 反転できる回数) は 0を下回ってはならない

実装

n, k = [int(x) for x in input().split()]
s = input()

# LとRが変化する場所の数を数える
# 同じ向きに並んでいるものは1人として考える(反転しても結果が変わらない)
# LとRが変わる箇所同士で反転させると2人がHappyになる
change_point = 0
for i in range(n-1):
    if s[i] != s[i+1]:
        change_point += 1

# 端っこの人は必ず幸せではないため n - 1
# k回まで幸せな人を2人ずつ増やせる
ans = n - 1 - max(change_point - 2 * k, 0)
print(ans)

上記を図で示したもの(理解しきれなかったので書いてみた)

ABC140_D図示