Please sign in first.
Official
C - Move Segment Editorial
by
C - Move Segment Editorial
by
kyopro_friends
「\(K\) 番目の 1 の塊」と「その直前の 0 の塊」を入れ替えたものが答えとなります。
したがって、以下のアルゴリズムにより問題を解くことができます
0と1の境界で文字列を分割- \(K\) 番目の
1の塊とその前の塊を入れ替える - 文字列を連結する
入力例1:
010011100011001 ↓ split 0 1 00 111 000 11 00 1 ↓ swap 0 1 00 111 11 000 00 1 ↓ join 010011111000001
実装例(Python)
N,K = map(int,input().split())
S = input()
# split
idx = [0] + [i for i in range(1,N) if S[i-1]!=S[i]] + [N]
splited_S = [S[idx[i]:idx[i+1]] for i in range(len(idx)-1)]
# swap
if S[0] == '0':
kth_1_idx = 2*K-1
else:
kth_1_idx = 2*K-2
splited_S[kth_1_idx-1], splited_S[kth_1_idx] = splited_S[kth_1_idx], splited_S[kth_1_idx-1]
# join
T = "".join(splited_S)
print(T)
posted:
last update:
