Official

C - Move Segment Editorial by kyopro_friends


\(K\) 番目の 1 の塊」と「その直前の 0 の塊」を入れ替えたものが答えとなります。

したがって、以下のアルゴリズムにより問題を解くことができます

  1. 01 の境界で文字列を分割
  2. \(K\) 番目の 1 の塊とその前の塊を入れ替える
  3. 文字列を連結する

入力例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: