Problem:


Score : 400 points

Problem Statement

There are N people standing in a queue from west to east.

Given is a string S of length N representing the directions of the people.
The i-th person from the west is facing west if the i-th character of S is L, and east if that character of S is R.

A person is happy if the person in front of him/her is facing the same direction.
If no person is standing in front of a person, however, he/she is not happy.

You can perform the following operation any number of times between 0 and K (inclusive):

Operation: Choose integers l and r such that 1 \leq l \leq r \leq N, and rotate by 180 degrees the part of the queue: the l-th, (l+1)-th, ..., r-th persons. That is, for each i = 0, 1, ..., r-l, the (l + i)-th person from the west will stand the (r - i)-th from the west after the operation, facing east if he/she is facing west now, and vice versa.

What is the maximum possible number of happy people you can have?

Constraints

N is an integer satisfying 1 \leq N \leq 10^5.

K is an integer satisfying 1 \leq K \leq 10^5.

|S| = N

Each character of S is L or R.

Input

Input is given from Standard Input in the following format:

N K
S

Output

Print the maximum possible number of happy people after at most K operations.

Sample Input 1

6 1
LRLRRL

Sample Output 1

3

If we choose (l, r) = (2, 5), we have LLLRLL, where the 2-nd, 3-rd, and 6-th persons from the west are happy.

Sample Input 2

13 3
LRRLRLRRLRLLR

Sample Output 2

9

Sample Input 3

10 1
LLLLLRRRRR

Sample Output 3

9

Sample Input 4

9 2
RRRLRLRLL

Sample Output 4

7



Sample input:
6 1
LRLRRL


Sample output:
3

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import heapq

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""


N, K = list(map(int, input().split()))
S = input()
    
def main():
    res = N
    past = S[0]
    cnt = K
    
    if N == 2:
        if S[0] == "R" and S[1] == "L" and S[0] == "L" and S[1] == "R":
            return print(0)
        if S[0] == "R" and S[1] == "R" and S[0] == "L" and S[1] == "L":
            return print(1)
    
    for n in range(1, N):
        now = S[n]
        print(past, now)
        if past == "R" and now == "L":
            print(n, ": BAD")
            res -= 2
            if 0 < cnt:
                res+= 2
                cnt -= 1
        past = now
    if S[0] == "L":
        print(0, ": BAD")
        res -= 1
        if 0 < cnt:
            res += 1
            cnt -= 1
    if S[-1] == "R":
        print(N-1, ": BAD")        
        res -= 1
        if 0 < cnt:
            res += 1
            cnt -= 1
        
        
    return print(res)
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = list(input())
S_2 = []; S_2.append(S[0])
ans = 0
for i in range(N - 1):
    if S[i+1] != S_2[-1]:
        S_2.append(S[i+1])
    if S[i+1] == S[i]:
        ans += 1

num_lr = len(S_2)   # L集合・R集合の数の合計
num = num_lr // 2   # 便宜的に左端がL集合としたとき、R集合だけを操作できる回数

if num_lr == 1:
    ans = ans
elif num_lr % 2 == 0:
    if num > K:
        ans += (K * 2)
    elif num <= K:
        ans += ((K * 2) - 1)
elif num_lr % 2 == 1:
    if num >= K:
        ans += (K * 2)
    elif num < K:
        ans += (num * 2)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, K = map(int, input().split())
    S = input().rstrip()

    if N == 1:
        print(0)
        return
    if N <= 3:
        print(N - 1)
        return

    if S == ''.join(sorted(S)) or S == ''.join(sorted(S))[:: -1]:
        print(N - 1)
        return

    RLcnt = S.count('RL')

    if RLcnt == 0:
        print(N - 1)
        return

    add = min(K, RLcnt) * 2

    if RLcnt <= K:
        if S[0] == 'R' and S[1] == 'L':
            add -= 1
        if S[-1] == 'L' and S[-2] == 'R':
            add -= 1
    if RLcnt - 1 == K:
        if S[0] == 'R' and S[1] == 'L' and S[-1] == 'L' and S[-2] == 'R':
            add -= 1

    ans = 0
    for i in range(N - 1):
        if S[i] == 'R' and S[i + 1] =='R':
            ans += 1
    for i in range(1, N)[:: -1]:
        if S[i] == 'L' and S[i - 1] == 'L':
            ans += 1

    ans = min(N - 1, ans + add)
    print(ans)

sol()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import heapq

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""


N, K = list(map(int, input().split()))
S = input()
    
def main():
    res = N
    past = S[0]
    cnt = K
    cnt2= 0
    for n in range(1, N):
        now = S[n]
        #print(past, now)
        if past == "R" and now == "L":
            #print(n, ": BAD")
            res -= 2
            if 0 < cnt:
                res+= 2
                cnt -= 1
        past = now
    tmp = res
    if S[0] == "L":
        #print(0, ": BAD")
        res -= 1
        cnt2+= 1
        if 0 < cnt:
            res += 1
            cnt -= 1
    if S[-1] == "R":
        #print(N-1, ": BAD")        
        res -= 1
        cnt2+= 1
        if 0 < cnt:
            res += 1
            cnt -= 1
    if cnt2 == 2 and 2 < cnt and tmp == N-2:
        res -= 2
        
        
    return print(res)
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, K = map(int, input().split())
    S = input().rstrip()

    if N == 1:
        print(0)
        return
    if N <= 3:
        print(N - 1)
        return

    if S == ''.join(sorted(S)) or S == ''.join(sorted(S))[:: -1]:
        print(N - 1)
        return

    RLcnt = S.count('RL')

    if RLcnt == 0:
        print(N - 1)
        return

    add = 2 * min(K, RLcnt)
    if S[0] == 'R' and S[1] == 'L':
        add -= 1
    if S[-1] == 'L' and S[-2] == 'R':
        add -= 1

    ans = 0
    for i in range(N - 1):
        if S[i] == 'R' and S[i + 1] =='R':
            ans += 1
    for i in range(1, N)[:: -1]:
        if S[i] == 'L' and S[i - 1] == 'L':
            ans += 1

    ans = min(N - 1, ans + add)
    print(ans)

sol()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, K = map(int, input().split())
    S = input().rstrip()

    if N == 1:
        print(0)
        return

    if S == ''.join(sorted(S)) or S == ''.join(sorted(S))[:: -1]:
        print(N - 1)
        return

    RLcnt = S.count('RL')

    if RLcnt == 0:
        print(N - 1)
        return

    add = 2 * min(K, RLcnt)

    ans = 0
    for i in range(N - 1):
        if S[i] == 'R' and S[i + 1] =='R':
            ans += 1
    for i in range(1, N)[:: -1]:
        if S[i] == 'L' and S[i - 1] == 'L':
            ans += 1

    ans = min(N - 1, ans + add)
    print(ans)

sol()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, K = map(int, input().split())
    S = input().rstrip()

    if N == 1:
        print(0)
        return

    RLcnt = S.count('RL')

    if RLcnt == 0:
        print(N - 1)
        return

    add = 2 * min(K, RLcnt)

    ans = 0
    for i in range(N - 1):
        if S[i] == 'R' and S[i + 1] =='R':
            ans += 1
    for i in range(1, N)[:: -1]:
        if S[i] == 'L' and S[i - 1] == 'L':
            ans += 1

    ans = min(N - 1, ans + add)
    print(ans)

sol()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

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

    if N == 1:
        print(0)
        return

    RLcnt = S.count('RL')

    if RLcnt <= 1:
        print(N - 1)
        return

    add = 2 * min(K, RLcnt)

    ans = 0
    for i in range(N - 1):
        if S[i] == 'R' and S[i + 1] =='R':
            ans += 1
    for i in range(1, N)[:: -1]:
        if S[i] == 'L' and S[i - 1] == 'L':
            ans += 1

    ans += add
    print(ans)


sol()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

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

    RLcnt = S.count('RL')

    if RLcnt == 0:
        print(N - 1)
        return

    add = 2 * min(K, RLcnt)

    ans = 0
    for i in range(N - 1):
        if S[i] == 'R' and S[i + 1] =='R':
            ans += 1
    for i in range(1, N)[:: -1]:
        if S[i] == 'L' and S[i - 1] == 'L':
            ans += 1

    ans += add
    print(ans)


sol()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import heapq

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""


N, K = list(map(int, input().split()))
S = input()
    
def main():
    res = N
    past = S[0]
    cnt = K
    for n in range(1, N):
        now = S[n]
        #print(past, now)
        if past == "R" and now == "L":
            #print(n, ": BAD")
            res -= 2
            if 0 < cnt:
                res+= 2
                cnt -= 1
        past = now
    if S[0] == "L":
        #print(0, ": BAD")
        res -= 1
        if 0 < cnt:
            res += 1
            cnt -= 1
    if S[-1] == "R":
        #print(N-1, ": BAD")        
        res -= 1
        if 0 < cnt:
            res += 1
            cnt -= 1
        
    return print(res)
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
b = S[0]
c = 0
for i in range(1, N):
  if b != S[i]:
    c += 1
    b = S[i]
b = S[0]
result = min(c, K) * 2
if c == K:
  result -= 1
for i in range(1, N):
  if S[i] == b:
    result += 1
  else:
     b = S[i]
print(result)

Submission status: Wrong Answer

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

dup = 0
for i in range(1,N):
    if S[i] == S[i-1]:
        dup += 1
#print(min(N-1, dup + K*2))
print(dup + K * 2)

Submission status: Wrong Answer

Solution code:
n,k = (int(i) for i in input().split())  
string = input()
s = [string[i] for i in range(len(string))]

count = 0
first = False
end = False

if s[0] == 'L':
    first = True

if s[-1] == 'R':
    end = True

for i in range(len(s)):
    d = s[i]
    if d == 'L' and i>0 and s[i-1]=='L':
        count += 0
    elif d == 'R' and i<n-1 and s[i+1]=='R':
        count += 0
    else:
        count += 1

for i in range(k):
    if count-2 >= 2:
        count += -2
    else:
        if first:
            count += -1
            first = False
        elif end:
            count += -1
            end = False
        else:
            count += -2

if count < 1:
    count = 1
    
print(n-count)

Submission status: Wrong Answer

Solution code:
n,k = (int(i) for i in input().split())  
string = input()
s = [string[i] for i in range(len(string))]

count = 0
first = False
end = False

if s[0] == 'L':
    first = True

if s[-1] == 'R':
    end = True
print(first)
print(end)

for i in range(len(s)):
    d = s[i]
    if d == 'L' and i>0 and s[i-1]=='L':
        count += 0
    elif d == 'R' and i<n-1 and s[i+1]=='R':
        count += 0
    else:
        count += 1
print(count)
for i in range(k):
    if count-2 >= 2:
        count += -2
    else:
        if first:
            count += -1
            first = False
        elif end:
            count += -1
            end = False
        else:
            count += -2

if count < 1:
    count = 1
    
print(n-count)

Submission status: Wrong Answer

Solution code:
n,k = (int(i) for i in input().split())  
string = input()
s = [string[i] for i in range(len(string))]

count = 0
first = False
end = False

if s[0] == 'L':
    first = True

if s[-1] == 'R':
    end = True

for i in range(len(s)):
    d = s[i]
    if d == 'L' and i>0 and s[i-1]=='L':
        count += 0
    elif d == 'R' and i<n-1 and s[i+1]=='R':
        count += 0
    else:
        count += 1

for i in range(k):
    if count-2 >= 2:
        count += -2
    else:
        if first:
            count += -1
            first = False
        elif end:
            count += -1
            end = False
        else:
            count += -2

if count < 0:
    count = 0
    
print(n-count)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
R = []
L = []
direction = S[0]
cnt = 1
for i in range(1, N):
    if S[i] == direction:
        cnt += 1
    else:
        if direction == 'L':
            L.append(cnt)
        else:
            R.append(cnt)
        cnt = 1
        direction = S[i]
if direction == 'L':
    L.append(cnt)
else:
    R.append(cnt)
# print(L, R)
res = [0,0]
L_before = sum(L) - len(L)
R_before = sum(R) - len(R)
if len(L) >= K:
    K_L = sorted(L)[-K:]
    res[0] = R_before + sum(K_L) + len(K_L)
else:
    res[0] = R_before + sum(L) + len(L)
if len(R) >= K:
    K_R = sorted(R)[-K:]
    res[1] = L_before + sum(K_R) + len(K_R)
else:
    res[1] = L_before + sum(R) + len(R)
print(max(res))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
R = []
L = []
direction = S[0]
cnt = 1
for i in range(1, N):
    if S[i] == direction:
        cnt += 1
    else:
        if direction == 'L':
            L.append(cnt)
        else:
            R.append(cnt)
        cnt = 1
        direction = S[i]
if direction == 'L':
    L.append(cnt)
else:
    R.append(cnt)
# print(L, R)
L_res = 0
R_res = 0
L_before = sum(L) - len(L)
R_before = sum(R) - len(R)
if len(L) >= K:
    K_L = sorted(L)[-K:]
    L_res = R_before + sum(K_L) + len(K_L)
if len(R) >= K:
    K_R = sorted(R)[-K:]
    R_res = L_before + sum(K_R) + len(K_R)
print(max(R_res, L_res))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = input()
R = []
L = []
direction = S[0]
cnt = 1
for i in range(1, N):
    if S[i] == direction:
        cnt += 1
    else:
        if direction == 'L':
            L.append(cnt)
        else:
            R.append(cnt)
        cnt = 1
        direction = S[i]
if direction == 'L':
    L.append(cnt)
else:
    R.append(cnt)
# print(L, R)
L_res = 0
R_res = 0
L_before = sum(L) - len(L)
R_before = sum(R) - len(R)
if len(L) >= K:
    K_L = sorted(L)[-K:]
    L_res = R_before + sum(K_L) + len(K_L)
    if L[0] in K_L:
        L_res -= 1
        if len(L) > K:
            if sorted(L)[-K - 1] == L[0]:
                L_res += 1
if len(R) >= K:
    K_R = sorted(R)[-K:]
    R_res = L_before + sum(K_R) + len(K_R)
    if R[-1] in K_R:
        R_res -= 1
        if len(R) > K:
            if sorted(R)[-K - 1] == R[-1]:
                R_res += 1
print(max(R_res, L_res))

Submission status: Wrong Answer

Solution code:
from itertools import*

n,k,a=open(0).read().split()
n,k=int(n),int(k)*2+1
ar=[len(list(v))for k,v in groupby(a)]

#print(ar)
if n<=k:
    print(sum(ar)-1)
else:
    ar2=[i-1 for i in ar]
    print(max(sum(ar2[i%2:i:2])+sum(ar[i:i+k])-1+sum(ar2[i+k+2::2])for i in range(n-k+1)))

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
s = input()
ans = 0
RL = 0
LR = 0
for i in range(1, n):
    if s[i-1] == s[i]:
        ans += 1
    if s[i-1] + s[i] == "RL":
        RL += 1
k = min(k, RL)
ans += k*2
if k == RL:
    ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
s = input()
ans = 0
RL = 0
LR = 0
for i in range(1, n):
    if s[i-1] == s[i]:
        ans += 1
    if s[i-1] + s[i] == "RL":
        RL += 1
k = min(k, RL)
print(ans + k*2)

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
s = input()
ans = 0
RL = 0
LR = 0
for i in range(1, n):
    if s[i-1] == s[i]:
        ans += 1
    if s[i-1] + s[i] == "RL":
        RL += 1
ans += min(k*2, RL*2)
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
s = input()
ans = 0
RL = 0
LR = 0
for i in range(1, n):
    if s[i-1] == s[i]:
        ans += 1
    if s[i-1] + s[i] == "RL":
        RL += 1
    if s[i-1] + s[i] == "LR":
        LR += 1
while RL > 0:
    if not k:
        break
    k -= 1
    if LR:
        RL -= 1
        LR -= 1
        ans += 2
    else:
        ans += 1
while LR > 0:
    if not k:
        break
    k -= 1
    LR -= 1
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = [int(v) for v in input().split(' ')]
S = input()

A = []
for s in S:
    if s == 'L':
        A.append(0)
    else:
        A.append(1)

def count(S):
    prev_s = 1
    s = 1
    next_s = A[0]

    c = 0
    i = 1
    while i <= N:
        prev_s = s
        s = next_s
        if i < N:
            next_s = A[i]
        else:
            next_s = 0

        if s == 0: # L
            if s != prev_s:
                c += 1
        else: # R
            if s != next_s:
                c += 1
        i += 1
    return c

c = count(S)
# print(c)
print(N - (c - K * 2))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

last = ''
sep_idcs = [0]
base_happiness = 0
for i, c in enumerate(S):
    if i != 0:
        if last != c:
            base_happiness += i - sep_idcs[-1] - 1
            sep_idcs.append(i)
    last = c
# The right edge
len_seps = len(sep_idcs)
if len_seps == 3:
    base_happiness -= 1

# print(sep_idcs)
if len_seps % 2 and K == len_seps / 2:
    print(base_happiness + 2 * K - 1)
else:
    print(base_happiness + 2 * K)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

last = ''
sep_idcs = [0]
base_happiness = 0
for i, c in enumerate(S):
    if i != 0:
        if last != c:
            base_happiness += i - sep_idcs[-1] - 1
            sep_idcs.append(i)
    last = c
# The right edge
len_seps = len(sep_idcs)
if len_seps == 3:
    base_happiness -= 1

print(sep_idcs)
if len_seps % 2 and K == len_seps / 2:
    print(base_happiness + 2 * K - 1)
else:
    print(base_happiness + 2 * K)

Submission status: Wrong Answer

Solution code:
n, k = map(int,input().split())
s = input()
ans = 0
LR, RL = 0, 0
for i in range(1, n):
    if s[i-1] + s[i] == "LR":
        LR += 1
    if s[i-1] + s[i] == "RL":
        RL += 1
    if min(LR, RL) > 0:
        LR -= 1
        RL -= 1
        ans += 2
        LR, RL = RL, LR
        k -= 1
        if not k:
            break
S = list(s)
cnt = 0
for i in range(1, n):
    if S[i-1] != S[i]:
        cnt += 1
if cnt == 0 or (k and cnt == 1):
    print(n-1)
    import sys
    sys.exit()
for i in range(1, n):
    if k and S[i-1] + S[i] == "RL":
        k -= 1
        S[i-1] = "L"
for i in range(1, n):
    if k and S[i-1] + S[i] == "LR":
        k -= 1
        S[i] = "R"
for i in range(1, n):
    if S[i-1] == S[i]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import re
a = input().split(' ')
N = int(a[0])
K = int(a[1])
S = input()

LR = re.findall(r'LR', S)
RL = re.findall(r'RL', S)

num1 = len(LR)
num2 = len(RL)

if num1 < num2:
  num = num1
else:
  num = num2
  
if K < num:
  num = K
  
if (num1 - num2 == 1) or (num2 - num1 == 1):
  point = num * 2 + 1
else:
  point = num * 2
  
for i in range(N):
  if i != 0:
    if S[i] == S[i-1]:
      point = point + 1


print(point)