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: Runtime Error

Solution code:
n,k = map(int,input().split())
s = input()
l = []
for i in range(len(s)-1):
  if s[i] == s[i+1]:
    l.append(i)
    l.append(i+1)
  else:
    p = i
    
l = sorted(list(set(range(1,len(s)-1)) - set(l)))
s = list(s)
if l == []: 
  l = [0,p]
if len(l) == 1:
  l.append(len(s)-1)
for i in range(l[0],l[-1]+1):
  if s[i] == "L":
    s[i] = "R"
  else:
    s[i] = "L"
for j in range(k-1):
  for i in range(l[0],l[-1]+1):
    if s[i] == s[i+1]:
      l.append(i)
      l.append(i+1)
    else:
      p = i
  l = sorted(list(set(range(1,len(s)-1)) - set(l)))
  if l == []: 
    l = [0,p]
  if len(l) == 1:
    l.append(len(s)-1)
  s = list(s)
  for i in range(l[0],l[-1]+1):
    if s[i] == "L":
      s[i] = "R"
    else:
      s[i] = "L"
c = 0
for i in range(len(s)-1):
  if s[i] == s[i+1]:
    c += 1
print(c)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = [si for si in input()]


def hn(lst):
    cnt = 0
    for i in range(0, n):
        if lst[i] == 'L':
            if i > 0:
                if lst[i - 1] == 'L':
                    cnt += 1
        else:
            if i < n - 1:
                if lst[i + 1] == 'R':
                    cnt += 1
    return cnt, lst


def op(lst, l, r):
    nlst = [li for li in lst]

    for i in range(0, r - l + 1):
        if lst[l + i - 1] == 'L':
            nlst[r - i - 1] = 'R'

        else:
            nlst[r - i - 1] = 'L'

    return nlst


def tryop(best, lst, cnt):
    if cnt >= k:
        print(best)
        return best

    for i in range(1, n):
        for j in range(i, n):
            res = hn(op(lst, i, j))
            if res[0] > best:
                best = res[0]
                best_res = res[1]

    tryop(best, best_res, cnt + 1)


tryop(0, lst=s, cnt=0)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
S = input()
lCnt = S.count('L')
rCnt = S.count('R')
tmp = ''
if lCnt < rCnt:
    tmp = 'L'
else:
    tmp = 'R'

sindex = 0
eindex = 0
secnt = 0
anslst = [list([0] * 3) for i in range(N)]

for i in range(N):
    if sindex == 0:
        if S[i] == tmp:
            sindex = i
        else:
            complex
    else:
        if S[i] != tmp:
            eindex = i - 1
            anslst[i][0] = sindex
            anslst[i][1] = eindex
            anslst[i][2] = eindex - sindex + 1
            sindex = 0
            eindex = 0
if sindex != 0:
    eindex = N - 1
    anslst[N - 1][0] = sindex
    anslst[N - 1][1] = eindex
    anslst[N - 1][2] = eindex - sindex + 1
anslst.sort(key=lambda x: x[2], reverse=True)

if tmp == 'R':
    tmp = 'L'
else:
    tmp = 'R'

for i in range(K):
    S = S[0:anslst[i][0]] + (tmp * anslst[i][2]) + S[anslst[i][1] + 1:]

ans = 0
if K == 1:
    for i in range(N - 1):
        if S[i] == tmp:
            if S[i] == S[i + 1]:
                ans += 1
else:
    for i in range(1, N - 1):
        if S[i] == tmp:
            if S[i] == S[i + 1]:
                ans += 1
    ans += anslst[0][2]

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

# find the largest subsequence
packet = []
direction = [S[0]]
seq = 1
for i in range(1, N - 1):
    if S[i] == direction[-1]:
        seq += 1
    else:
        packet.append(seq)
        seq = 1
        direction.append(S[i])
if S[N - 1] == direction[-1]:
    seq += 1
    packet.append(seq)
else:
    packet.append(seq)
    seq = 1
    direction.append(S[N - 1])
    packet.append(seq)

#print(packet)


start_color = S[0]
packet_len = len(packet)

max_sum = packet[0] + packet[1]
max_idx = 0
for i in range(1, packet_len - 1):
    if max_sum < packet[i - 1] + packet[i] + packet[i + 1]:
        max_sum = packet[i - 1] + packet[i] + packet[i + 1]
        max_idx = i
if max_sum < packet[packet_len - 2] + packet[packet_len - 1]:
    max_idx = packet_len - 1


for _ in range(K):
    if packet_len == 1:
        print(packet_len - 1)
        exit()
    #print(max_idx)

    if max_idx == 0:
        val = packet[0] + packet[1]
        packet = [val] + packet[2:]
        packet_len -= 1

    elif max_idx == packet_len - 1:
        val = packet[-1] + packet[-2]
        packet = packet[:packet_len - 2] + [val]
        packet_len -= 1
        max_idx = packet_len - 2
    else:
        val = packet[max_idx - 1] + packet[max_idx] + packet[max_idx + 1]
        packet = packet[:max_idx - 1] + [val] + packet[max_idx + 2:]
        packet_len -= 2
        max_idx = max_idx - 1

    #print(packet)

ans = 0
for v in packet:
    ans += v - 1
print(ans)

Submission status: Runtime Error

Solution code:

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

S = input()

if N == 1:
    print(0)
    exit()
#左端をLにする場合
now = ""
num_substr = 0
ex = ""
stack = []
for i in range(N):
    if (ex == "L" or ex == "") and S[i] == "R":
        start = i
    if ex == "R" and S[i] == "L":
        end = i-1
        stack.append((start, end))
        num_substr += 1
    ex = S[i]
#左からひっくり返す
if num_substr == 0:
    print(N-1)
    exit()
tmp = min(K,num_substr,N)
num = stack[tmp-1][1]
ss = "L"*(num+1)+S[num+1:]
ll = num

for i in range(num+1,N):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            ll += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            ll += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            ll += 1


#右からひっくり返す
if num_substr == 0:
    print(N-1)
    exit()
tmp = min(K,num_substr,N)
num = stack[len(stack)-tmp][0]
ss = S[:(N-1-num)]+"L"*(N-1-num)

lr = (N-1-num)

for i in range(num):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            lr += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            lr += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            lr += 1


######################################################################
#左端をRにする場合
now = ""
num_substr = 0
ex = ""
stack = []
for i in range(N):
    if (ex == "R" or ex == "") and S[i] == "L":
        start = i
    if ex == "L" and S[i] == "R":
        end = i-1
        stack.append((start, end))
        num_substr += 1
    ex = S[i]
#左からひっくり返す
if num_substr == 0:
    print(N-1)
    exit()
tmp = min(K,num_substr,N)
num = stack[tmp-1][1]
ss = "R"*(num+1)+S[num+1:]
rl = num
#print(ll, tmp)
for i in range(num+1,N):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            rl += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            rl += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            rl += 1


#右からひっくり返す
if num_substr == 0:
    print(N-1)
    exit()
tmp = min(K,num_substr,N)
num = stack[len(stack)-tmp][0]
ss = S[:(N-1-num)]+"R"*(N-1-num)

rr = (N-1-num)
#print(ll, tmp)
for i in range(num):
    if i == 0:
        if (ss[i+1] == "R" and ss[i] == "R"):
            rr += 1
    elif i == N-1:
        if (ss[i-1] == "L" and ss[i] == "L"):
            rr += 1
    else:
        if (ss[i-1] == "L" and ss[i] == "L") or (ss[i+1] == "R" and ss[i] == "R"):
            rr += 1


print(max([ll,lr,rl,rr]))

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin.readline
na = lambda: map(int, stdin().split())
ns = lambda: stdin().rstrip()
ni = lambda: int(ns())
def main():
  n, k = na()
  s = ns()+"0"

  ans = 0
  LRcnt = []
  cnt = 1
  LR = []
  for i in range(n):
    if s[i] == s[i+1]:
      ans += 1
      cnt += 1
    else:
      LR.append(s[i])
      LRcnt.append(cnt)
      cnt = 1

  N = len(LRcnt)
  wa = [0] * (N+1)
  for i in range(N):
    wa[i+1] = wa[i] + LRcnt[i]

  ans = 0
  for i in range(N-k-2):
    x = wa[i+k+2] - wa[i] - 1 + sum(LRcnt[i+k+2:]) - len(LRcnt[i+k+2:]) + sum(LRcnt[:i+k+2]) - len(LRcnt[:i+k+2])
    if ans < x:
      ans = x
      if LR[i] == "R":
        ans -= 1
      if LR[i+k+1] == "L"::
        ans += 1

  if ans == 0:
    print(sum(LRcnt)-1)
  else:
    print(ans)
main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = input()
s = list(s)
print(s)
before = s[1]
flag = False
place = -1
end = -1
cnt = 0

for i in range(1, n-1) :

    if s[i] != before :
        flag = True
        place = i

    if flag :
        print(s, i)
        if i + 1 == n - 1 :
            if s[place] == s[i+1] :
                end = i+1
            else :
                end = i
            print(s, i, end, 'end')
            if s[place] == 'L' :
                if end == i :
                    s[place:end] = 'R'
                else :
                    s[place:end] = 'R'
                    #s[end-1] ='R'
            else :
                if end == i :
                    s[place:end] = 'L'
                else :
                    s[place:end] = 'L'
                    #s[end-1] = 'L'
            print(s, 'end2')
            cnt += 1
            if cnt == k :
                break
            flag = False
            before = s[i]
            continue

        if s[i] != s[i+1] :
            print(s)
            if s[place] == 'L' :
                s[place:i+1] = 'R'
            else :
                s[place:i+1] = 'L'

            cnt += 1
            print(s)
            if cnt == k:
                break
            flag = False
            before = s[i]
            continue
    before = s[i]

print(s)
if cnt != k :
    if s[0] != s[1] :
        s[0] = s[1]
    if k >= cnt + 2 :
        if s[n-1] != s[n-2] :
            s[n-1] = s[n-2]

seqCnt = 0
ans = 0
print(s)
for i in range(n-1) :
    print(i, seqCnt)
    if s[i] == s[i+1] :
        seqCnt += 1
    if s[i] != s[i+1] or i == n - 2 :
        print(ans, seqCnt, i)
        if seqCnt >= 1 :
            ans += seqCnt
        seqCnt = 0

print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
S = input()
ss = [1 if S[i] == S[0] else 0 for i in range(N)]
index = 0
for i in range(K):
    index = ss[index+1:N].index(1)+index+1
    ss[1:index] = [1] * len(ss[1:index])
count = 1
for i in range(1,N):
    count += 1
    if ss[i] != ss[i-1]:
        count -= 1
print(count-1)

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
char_org = list(input())
point_R = 0
point_L = 0

for m in range(K):
    char = char_org
    std = "R"
    char_rev = list(reversed(char))
    for i in range(len(char)):
        if std == char[i]:
            pass
        else:
            left = i
            break

    for j in range(len(char_rev)):
        if std == char_rev[j]:
            pass
        else:
            right = len(char) - j
            break
    rotate = char[left:right]
    rotate_rev = list(reversed(rotate))

    for k in range(len(rotate_rev)):
        if rotate_rev[k] == "R":
            rotate_rev[k] = "L"
        elif rotate_rev[k] == "L":
            rotate_rev[k] = "R"

    for l in range(len(char)):
        if left <= l < right:
            char[l] = rotate_rev[l-left]
for n in range(1,len(char)):
    if char[n] == char[n-1]:
        point_R += 1


for m in range(K):
    char = char_org
    std = "L"
    char_rev = list(reversed(char))
    for i in range(len(char)):
        if std == char[i]:
            pass
        else:
            left = i
            break

    for j in range(len(char_rev)):
        if std == char_rev[j]:
            pass
        else:
            right = len(char) - j
            break
    rotate = char[left:right]
    rotate_rev = list(reversed(rotate))

    for k in range(len(rotate_rev)):
        if rotate_rev[k] == "R":
            rotate_rev[k] = "L"
        elif rotate_rev[k] == "L":
            rotate_rev[k] = "R"

    for l in range(len(char)):
        if left <= l < right:
            char[l] = rotate_rev[l-left]

for n in range(1,len(char)):
    if char[n] == char[n-1]:
        point_L += 1
print(max(point_L,point_R))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = input()

l_array = [0 for x in range(n)]
l_reverse = []
r_array = [0 for x in range(n)]
r_reverse = []

cnt = []
l_cnt = 0
r_cnt = 0
now = s[0]
for index, ss in enumerate(s):
    if ss == "L":
        if now == ss:
            l_cnt += 1
        else:
            cnt.append(r_cnt)
            r_cnt = 0
            l_cnt = 1
            now = "L"
    else:
        if now == ss:
            r_cnt += 1
        else:
            cnt.append(l_cnt)
            l_cnt = 0
            r_cnt = 1
            now = "R"
else:
    cnt.append(max(l_cnt, r_cnt))

len_cnt = len(cnt)
res = []
for i in range(0, len_cnt, 2):
    if i+1>=len_cnt: continue
    res.append(cnt[i]+cnt[i+1])
res = sorted(res, reverse=True)
ans = 0
for j in range(k):
    ans += res[j]
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
S = input()
T = [0 for z in range(n)]

for i in range(n):
  T[i] = S[i]

ans=[]

for r in range(n-2):
  for l in  range(n-1):
    y=0
    while r+y <= l-y:
      if S[r+y]=="R":
        T[l-y]="L"
      else:
        T[l-y]="R"
      y+=1
    
    cnt=0
    for j in range(n-1):
      if T[j]=="R" and T[j+1]=="L":
        cnt+=1
    ans.append(cnt)

print(max(ans))

Submission status: Runtime Error

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

def eval(line):
    prev = 0
    happiness = 0
    for d in line:
        if prev == d:
            happiness += 1

#        print((d,prev))
        prev = d
    return happiness

orig_score = eval(S)
mikomi = (N - orig_score) // 2
if mikomi < K:
    score = orig_score + mikomi*2
    
    if S[0] != S[1]:
        score += 1
        if K - mikomi > 1:
            if S[len(S)-2] != S[len(S)-1]:
                score += 1
    elif S[len(S)-2] != S[len(S)-1]:
        score += 1
    
else:
    score = orig_score + K*2


    
print(score)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
S = list(input())
l_r_count = []
count = 0
l = 0
for i in range(1,N):
    if S[i] == S[i-1]:
        continue
    else:
        tmp = [l,i-1,i-1-l]
        l_r_count.append(tmp)
        l = i
l_r_count.sort(key=lambda x: x[2])
l_r_count.reverse()

for j in range(K):
    left = l_r_count[j][0]
    right = l_r_count[j][1]
    change = S[left-1]
    for k in range(left,right+1):
        S[k] = change

happy = 0
for l in range(N):
    if 0<l and S[l] == "L" and S[l-1] == S[l]:
        happy += 1
    elif l < N-1 and S[l]=="R" and S[l] == S[l+1]:
        happy += 1
print(happy)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np


def main():
    n, k = map(int, input().split())
    s = input()

    happiness_array = np.array([], dtype='int')
    happiness = 0

    for i in range(n - 1):
        if i == 0:
            if s[i] == 'L' and s[i + 1] == 'L':
                continue
        if i == n - 2:
            if s[i + 1] == 'R' and s[i] == 'R':
                continue

        if s[i] == s[i + 1]:
            happiness += 1
        else:
            happiness_array = np.append(happiness_array, happiness)
            if i == n - 2:
                if s[i + 1] != s[i]:
                    happiness_array = np.append(happiness_array, 0)
            happiness = 0

    for j in range(k):
        max_sum_of_three = 0
        place_of_change = 0
        if len(happiness_array) >= 3:
            for i in range(len(happiness_array) - 2):
                sum_of_three = happiness_array[i] + happiness_array[i + 1] + happiness_array[i + 2]
                if sum_of_three > max_sum_of_three:
                    max_sum_of_three = sum_of_three
                    place_of_change = i + 1
            happiness_array[i] += happiness_array[i + 1] + happiness_array[i + 2] + 2
            happiness_array = np.delete(happiness_array, i + 1)
            happiness_array = np.delete(happiness_array, i + 1)
        else:
            happiness_array[0] += happiness_array[0] + happiness_array[1] + 2
            happiness_array = np.delete(happiness_array, 1)

        if len(happiness_array) == 1:
            break
        
    ans1 = np.sum(happiness_array[0::2])
    ans2 = np.sum(happiness_array[1::2])
    ans = max(ans1, ans2)


    print(ans)

main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#ABC140 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
s = list(input())
l = []
cnt = 1
for i in range(1,n):
    if s[i-1] != s[i]:
        l.append((cnt,i-1))
        cnt = 0
    cnt += 1
l.append((cnt,i))
m = len(l)
if m//2 <= k:
    print(n-1)
    quit()
h = []
for i in range(m):
    if i == 0:
        heappush(h,(-(l[i][0]+l[i+1][0]),l[i][0],l[i][1]))
    elif i == m-1:
        heappush(h,(-(l[i][0] + l[i-1][0]),l[i][0],l[i][1]))
    else:
        heappush(h,(-(l[i][0] + l[i-1][0] + l[i+1][0]),l[i][0],l[i][1]))
ans = 0
for _ in range(min(k,len(h))):
    l,i,j = heappop(h)
    ans += -l-1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
B = list(map(int,input().split()))
cnt = B[0]+B[N-2]
for i in range(1,N-1):
    cnt += min(B[i-1],B[i])
print(cnt)

Submission status: Runtime Error

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

pp = 'x'
vC = []

for s in S:
    if pp == s:
        vC[-1] += 1
    else:
        vC.append(0)
        pp = s

# print(vC)

res = N - 1 - max((len(vC)+1)//2 - K, 0)
print(res)
N, K = map(int, input().split())
S = input()

pp = 'x'
vC = []

for s in S:
    if pp == s:
        vC[-1] += 1
    else:
        vC.append(0)
        pp = s

# print(vC)

res = N - 1 - max((len(vC)+1)//2 - K, 0)
print(res)

Submission status: Runtime Error

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

c=0
if N>2:
    for i in range(1,N-1):
        if S[i]=="L" and S[i-1]=="L":
            c+=1
        elif S[i]=="R" and S[i+1]=="R":
            c+=1
if S[0]=="R" and S[1]=="R":
    c+=1
if S[-1]=="L" and S[-2]=="L":
    c+=1
    
cLR=0
cRL=0
for i in range(len(S)-1):
    if S[i]=="L" and S[i+1]=="R":
        cLR+=1
    elif S[i]=="R" and S[i+1]=="L":
        cRL+=1

min0 = min([cLR,cRL])
        
print(min([K, min0])*2 + c)

Submission status: Runtime Error

Solution code:
#import numpy as np

N, K = map(int, input().split())
s = list(input()) 

done = 0


out = 0

#gid_list = []
#gnum_list = []
#gkukan_list = []
#
#cur_gid = 0
#cur_gnum = 0
#cur_gstart = 0

for i in range(N):
    cur_c = s[i]
    
    if s[i] == "L" and i >= 1 and s[i-1] == "L":
        out += 1
    elif s[i] == "R" and i <= N-2 and s[i+1] == "R":
        out += 1

#    if i >= 1:
#        if cur_c != before_c:
#            cur_gend =i-1
#            cur_gkukan = [cur_gstart, cur_gend]
#            gkukan_list.append(cur_gkukan)
#            cur_gstart = i
#
#            gnum_list.append(cur_gnum)
#            cur_gnum = 0
#
#            cur_gid += 1
#    
#    cur_gnum += 1
#    gid_list.append(cur_gid)
#
#    before_c = cur_c
#
#cur_gend =N-1
#cur_gkukan = [cur_gstart, cur_gend]
#gkukan_list.append(cur_gkukan)
#gnum_list.append(cur_gnum)
#len_g = len(gnum_list)



#for i in range(N):
#    if done < K:
#        if 1 <= i <= N-2:
#            # L(RL) -> LLL
#            if s[i-1] == "L" and s[i] == "R" and s[i+1] == "L":
#                s[i] = "L"
#                out += 2
#                done += 1
#    else:
#        break

#print("current", out, done, s)
i = 0
while i < N:
    if done < K:
        if 0 <= i <= N-2:
           # L(RL) -> LLL
            if s[i] == "L" and s[i+1] == "R":
                start_i = i+1
                i += 1

                found = True
                while s[i] == "R":
                    i += 1
                    if i >= N:
                        found = False
                        break
               
                # s[i] == "L" made

                if found:
                    end_i = i-1
                else:
                    #end_i = N-1
                    break
                
                for j in range(start_i, end_i+1):
                    s[j] = "L"

                #print("found", found, start_i, end_i)
                if found:
                    out += 2
                #else:
                #    out += 1
                #    break

                done += 1

                i -= 1 # s[i] == "R" ni modosu
        else:
            pass
            #print("false", i)

        i += 1
    else:
        break


for i in range(N):
    if done < K:
        if 1 <= i <= N-2:
            # R(LR) -> RRR
            if s[i-1] == "R" and s[i] == "L" and s[i+1] == "R":
                s[i] = "R"
                out += 2
                done += 1
    else:
        break

for i in range(N-1):
    if done < K:
        if s[i] == "R" and s[i+1] == "L":
            s[i] = "L"
            out += 1
            done += 1
    else:
        break



i = 0
if done < K:
    if s[0] == "R":
        start_i = 0
        i += 1

        found = True
        while s[i] == "R":
            i += 1
            if i >= N:
                found = False
                break

        if found:
            end_i = i-1
            for j in range(start_i, end_i+1):
                s[j] = "L"
            out += 1
            #print("test0")
            
        done += 1


i = N-1
if done < K:
    if s[i] == "L":
        end_i = i
        i -= 1

        found = True
        while s[i] == "L":
            i -= 1
            if i >= -1:
                found = False
                break

        if found:
            start_i = i-1
            for j in range(start_i, end_i+1):
                s[j] = "R"
            out += 1
            #print("test0")
            
        done += 1

print(out)

Submission status: Runtime Error

Solution code:
tmp = input()
tmp_s = [int(x.strip()) for x in tmp.split(' ')]
N = tmp_s[0]
K = tmp_s[1]
S = list(input())

S_keep = S
time_k = 0
count_list = []
k = 0
while k < K:
    k += 1
    for l in range(1, N):
        for r in reversed(range(1, N)):
            if 1 <= l <= r <= N:
                S[l-1:r] = reversed(S[l-1:r])
                for i in range(0, r-l):
                    if S[l+i] == 'L':
                        S[l+i] = 'R'
                    else:
                        S[l+i] = 'L'
                count = 0
                for j in range(0, N-1):
                    if S[j] == S[j+1]:
                        count += 1
                    count_list.append(count+1)
print(max(count_list))

                
                

            

                



            


'''
N = int(input())
tmp = input()
B = [int(x.strip()) for x in tmp.split(' ')]
wa = B[0]
for i in range(0, N-2):
    wa += min(B[i], B[i+1])
wa += B[N-2]
print(wa)
'''


#たとえば　0 153 10 10 23
#0 0 10 10 10 23
'''
tmp = input()
C = [int(x.strip()) for x in tmp.split(' ')]
tmpsum = sum(B)
for i in range(0, N-1):
    if A[i]+1 == A[i+1]:
        tmpsum += C[A[i]-1]
print(tmpsum)
'''



'''
import itertools

N = int(input())
lists = list(range(1, N+1))
for i in itertools.permutations(range(1, N+1)):




tmp = input()
H = [int(x.strip()) for x in tmp.split(' ')]
n = 0
lists = list()
lists.append(0)
count = 0
while n <= N-2:
    if H[n] >= H[n+1]:
        while H[n] >= H[n+1]:
            count += 1
            n += 1
            if n == N-1:
                lists.append(count)
                break
        lists.append(count)
        count = 0
    else:
        n += 1
print(max(lists))
'''
'''
1 2 3 4 5 6 7 8 9 10 11 12 13

'''

Submission status: Runtime Error

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

def eval(line):
    prev = 0
    happiness = 0
    for d in line:
        if prev == d:
            happiness += 1

#        print((d,prev))
        prev = d
    return happiness

orig_score = eval(S)
mikomi = (N - orig_score) // 2
if mikomi < K:
    score = orig_score + mikomi*2
    
    if S[0] != S[1]:
        score += 1
        if K - mikomi > 1:
            if S[len(S)-2] != S[len(S)-1]:
                score += 1
    elif  if S[len(S)-2] != S[len(S)-1]:
        score += 1
    
else:
    score = orig_score + K*2


    
print(score)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
s = input()

l = s.count("L")
r = s.count("R")
if l >= r:
    x = "R"
else:
    x = "L"

w = []
for i in range(n):
    if s[i] == x:
        w.append(i)

y = []
z = [w[0]]
for j in range(len(w)-1):
    if w[i] != w[i+1] - 1:
        y.append(z)
        z = [w[i+1]]
    else:
        z.append(w[i+1])

m = 0
if len(y) <= k:
    print(n-1)
else:
    notHappy = (len(y) - k) * 2 + 1
    print(n - notHappy)

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
char_org = list(input())
point_R = 0
point_L = 0

for m in range(K):
    char = char_org
    std = "R"
    char_rev = list(reversed(char))
    for i in range(len(char)):
        if std == char[i]:
            pass
        else:
            left = i
            break

    for j in range(len(char_rev)):
        if std == char_rev[j]:
            pass
        else:
            right = len(char) - j
            break
    rotate = char[left:right]
    rotate_rev = list(reversed(rotate))

    for k in range(len(rotate_rev)):
        if rotate_rev[k] == "R":
            rotate_rev[k] = "L"
        elif rotate_rev[k] == "L":
            rotate_rev[k] = "R"

    for l in range(len(char)):
        if left <= l < right:
            char[l] = rotate_rev[l-left]
for n in range(1,len(char)):
    if char[n] == char[n-1]:
        point_R += 1


for m in range(K):
    char = char_org
    std = "L"
    char_rev = list(reversed(char))
    for i in range(len(char)):
        if std == char[i]:
            pass
        else:
            left = i
            break

    for j in range(len(char_rev)):
        if std == char_rev[j]:
            pass
        else:
            right = len(char) - j
            break
    rotate = char[left:right]
    rotate_rev = list(reversed(rotate))

    for k in range(len(rotate_rev)):
        if rotate_rev[k] == "R":
            rotate_rev[k] = "L"
        elif rotate_rev[k] == "L":
            rotate_rev[k] = "R"

    for l in range(len(char)):
        if left <= l < right:
            char[l] = rotate_rev[l-left]

for n in range(1,len(char)):
    if char[n] == char[n-1]:
        point_L += 1
print(max(point_L,point_R)

Submission status: Runtime Error

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

H0 = 0
N_LR = 0
N_RL = 0

if S[0] == 'R' and S[1] == 'R':
    H0 += 1
if S[0] == 'R' and S[1] == 'L':
    N_RL += 1
if S[0] == 'L' and S[1] == 'R':
    N_LR += 1

if S[N-1] == 'L' and S[N-2] == 'L':
    H0 += 1

for i in range(1, N-1):
    if S[i] == 'L' and S[i-1] == 'L' or S[i] == 'R' and S[i+1] == 'R':
        H0 += 1
    if S[i] == 'R' and S[i+1] == 'L':
        N_RL += 1
    if S[i] == 'L' and S[i+1] == 'R':
        N_LR += 1

M = min(N_RL, N_LR, K)
H1 = H0 + 2 * M
K -= M
N_RL -= M
N_LR -= M

result = H1 + min(K, N_RL, N_LR)
print(result)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 7)


def solve(N: int, K: int, S: str):
    S_list = list(S)
    L_num = 0
    R_num = 0
    small_num = 0
    popular_s = ''
    for i in S_list:
        if i == 'L':
            L_num += 1
        else:
            R_num += 1
    if L_num > R_num:
        popular_s = 'S'
        small_num = R_num
    else:
        popular_s = 'R'
        small_num = L_num

    if small_num <= K:
        print(N - 1)
    else:
        # ちゃんと解く
        a = []
        counter = -1
        result = 0
        before_s = ''
        for i in S_list:
            if i != popular_s:
                counter += 1
            else:
                a.append(counter)
                counter = 0
                if before_s == i:
                    result += 1
            before_s = i
        a.append(counter)

        #print(a)
        #print('tmp result', result)

        a_sorted = sorted(a)

        for i in range(K):
            b = a_sorted.pop()
            result += b + 1
        print(result)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, K, S)

if __name__ == '__main__':
    main()