ABC140 D - Face Produces Unhappiness

問題原文

問題要旨

一列に $N$ 人の人が並んでおり、各人は右か左を向いている。どの人も、目の前の人と同じ方向を向いていれば幸福を感じる。
以下の操作を $0$ 回以上 $K$ 回以下繰り返して、幸福な人の数を最大化せよ。

ある範囲の人の列を180度回転させる。（順番を反転させて、その後選んだ範囲の人の向きを逆にする。）
$1 \leq N, K \leq 10^{5}$

解法

操作がよくわからん

操作がややこしい。いろいろ実験して理解を深める。
例えば LLRRを選ぶと、まず順番反転して RRLL その後各人の向いている向きを逆にして、 LLRR 。あれ、元に戻った。 RLR ならどうか。まず順番反転して RLR その後各人の向いている向きを逆にして、 LRL 。少し変わった。
RLLLLLRだと？ → LRRRRL となる。どうやら範囲内の幸福な人の人数は変わらないことがわかる。

操作で幸福な人はどう変わる

？例えば LLRRRL だと、 3文字目から5文字目（RRR）に対して操作を行うと、 LLLLL にできる。この操作で、幸福な人は２人増えた。
範囲内の幸福な人の人数は変わらない + 操作で基本２人幸福な人が増えることがわかる。また、 LLLLL の幸福度は４なので、最大の幸福度が $N - 1$ であることもわかる。

どこを選んで反転させるべき？

LLLLRRRRLLLLRRRLLL などがあれば、これは RRRR と RRR を選ぶべき。
RRRRLLLLRRRRLLLRRR であれば、 LLLL と LLL。
RLRLRL であれば、 R の３つ or L の３つ。
結局 L or R の塊を選べばいいことがわかる。

結論

何回幸福度を増やす操作ができるか → min(Lの塊の数, Rの塊の数)
１操作につき幸福度は何増えるか → 基本２（端っこの時だけ１）
幸福度の上限は $N - 1$
より、 min(最初の状態の幸福度 + min(min(Lの塊の数, Rの塊の数), K) × 2, N - 1 ) が答えになる。

実装

N, K = map(int, input().split())
S = input()

ans = 0
for i in range(N):
    if S[i] == 'L':
        if i - 1 < 0:
            continue
        if S[i - 1] == 'L':
            ans += 1
    else:
        if i + 1 >= N:
            continue
        if S[i + 1] == 'R':
            ans += 1


X = min(len([s for s in S.split('L') if s != '']), len([s for s in S.split('R') if s != '']))
ans += min(X, K) * 2
print(min(ans, N - 1))

感想

割と苦手だけど、普通にいい問題。
端っこの処理とかがめんどくさく感じるけど、 「答えの上限値を知っておくことで、無駄な場合わけが減らせる」 ことがあることをしっかり覚えておきたい。

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。