ベスパリブ

ベスパもってないです。バイク買いました。

ABC 140: D問題の解説 (Python3)

問題:AtCoder Beginner Contest 140: D - Face Produces Unhappiness

公式解説PDF:https://img.atcoder.jp/abc140/editorial.pdf

公式解説動画:https://youtu.be/VSeggcnxwrc?t=3564

ABC140のD問題のPython3による解説です。

初見では全くわからず、解説動画の解説と言っても過言ではないのだ。

以下の解説は公式解説動画でやっていることほぼまんまなので、まずはそちらを視聴することをおすすめします。

解説

考察問題です。ランレングス法みたいな考え方をします。

与えられた文字列Sについて、Lが連続している部分列を「Lグループ」、Rが連続している部分列を「Rグループ」とし、LグループとRグループの塊に分けて考えます。すると、

  • LグループとRグループの境目を選択して操作をすると、基本的に幸福な人の数を+2できる
  • ただし、端っこの境目を選んだときのみ、+1になる
  • 一度の操作で幸福な人を増やせる数は最大で+2でしかない

ということに気づけばOKです。

以下は、入力例2について考えてみます。

## 初期状態
 L R R L R L R R L R L L R
   .         .         .     幸福な人:3## LグループとRグループの境目を選択して、操作をする

 L R R L R L R R L R L L R
  |___|

 L L L L R L R R L R L L R
   . . .     .         .     幸福な人:5## LグループとRグループの境目を選択して、操作をする

 L L L L R L R R L R L L R
        |_|

 L L L L L L R R L R L L R
   . . . . . .         .     幸福な人:7## LグループとRグループの境目を選択して、操作をする

 L L L L L L R R L R L L R
            |___|

 L L L L L L L L L R L L R
   . . . . . . . .     .     幸福な人:9## LグループとRグループの境目を選択して、操作をする

 L L L L L L L L L R L L R
                  |_|

 L L L L L L L L L L L L R
   . . . . . . . . . . .     幸福な人:11## LグループとRグループの境目を選択して、操作をする

 L L L L L L L L L L L L R
                        |_|

 L L L L L L L L L L L L L
   . . . . . . . . . . . .   幸福な人:12

以上の考察からすると、初期状態の幸福な人の数を score とすると、

  • K回操作して、さらに 2K 人を幸福にすることができたパターン = score + 2K
  • K回以下の操作で、すべての人を L(R) にすることができたパターン = N-1

のどちらかなので、最終的な幸福な人の数 ans は、

ans = min(score+2*K, N-1) 

となります。

コーナーケース

  • 特になし

実装

def solve():
    N, K = list(map(int, input().split()))
    S = input()

    ans = 0
    for i in range(N-1):
        if S[i] == S[i+1]:
            ans += 1

    ans = min(ans + 2*K, N-1)
    print(ans)


if __name__ == "__main__":
    solve()

初期状態の幸福な人の数 score をO(N)で数えればよいだけなので、計算量は  O(N)

TODO

解説PDFを読むと左端にRを、右端にLを置いて考える考察があります。解説PDFをシミュレートする実装をしたのですがコーナーケースっぽい testcase_19 でWAになったので、テストケースが公開されたら再考しようと思います。