✨
ABC140 D - Face Produces Unhappiness メモ[python]
URL
問題概要
一列にN人が並んでいる。それぞれ右か左を向いている。
目の前の人が自分で同じ方向を向いている時、その人は幸せとする。
l,l+1,...,r番目の人の列を反転させるという動作をk 回まで行える時
幸福な人の数は最大で何人にできるか？
提出コード
n, k = map(int, input().split())
s = input()
a = 0
for i in range(len(s) - 1):
if s[i] != s[i + 1]:
a += 1
print(len(s) - 1 - max(0, a - 2 * k))
考察
一回の反転で最大になるようなl,rを選ぶことは出来そうなものの複数回行える時の最大はわからずケンちょんさんの解説ブログをみた
ポイントとしては、
- 操作を最大 K 回まで行うことができる、系の問題では
- 一回の操作で何らかの値が規則的に変化する
- Greedyに順番にやっていく
という解法になることがほとんどらしい。
- スコア（幸福度）の言い換え
- 文字列中に存在する異なる文字が隣接する回数(LR or RL の個数)をa とすると スコア = N - a - 1 となる
このようにスコアの言い換えができると
- 反転操作では区間内の文字列のaの値は変わらない
- 区間の両端が同じ文字、かつその外側で文字が異なっている区間（LR...RL or RL...LR の両端削除）になっている区間を選んだ時のみ a の値は減少する。（a-=2)
であることが分かる
ここで、どのように区間を選んでいけばいいかを考えると、LorRが１つ以上連続する区間を順番に選んでいけば良い。
実装方針
解法が固まれば実装は簡単で、
- 文字列中のLとRの変わり目の個数 a を数える
- 最大 a は2*k まで減らすことができる。
- a = 1で操作可能な時は0にすることも可能
メモ
- 操作を最大k 回まで行える系の問題の解き方（今回はgreedy）
- スコアを適切な変数を使って数学的に表すことで言い換える
- 区間をどのように選ぶかで迷ったが一番シンプルなものを選ぶと良い（今回ならL or Rの連続列)
- 条件を満たす区間なら一回の操作でa が2だけ減るのは変わらない。
- 選び方が複数ある場合は一番シンプルなものを選ぶ（LRを両方含む区間だと反転後の区間のLRが考えにくい）
Discussion