キーワード
AtCoder Beginner Contest 380,
問題
0, 1 のみからなる長さ
N の文字列
S が与えられます。
S の中で先頭から
K 番目の 1 の塊を
K−1 番目の 1 の塊の直後まで移動した文字列を出力してください。
なお、
S には 1 の塊が
K 個以上含まれることが保証されます。
より正確な説明は以下の通りです。
S の
l 文字目から
r 文字目までからなる部分文字列を
S
l…r
と表す。
S の部分文字列
S
l…r
が 1 の塊であるとは、以下の条件を全て満たすことと定める。
S
l
=S
l+1
=⋯=S
r
= 1
l=1 または
S
l−1
= 0
r=N または
S
r+1
= 0
S に含まれる 1 の塊が
S
l
1
…r
1
,…,S
l
m
…r
m
で全てであり、
l
1
<⋯<l
m
を満たしているとする。
このとき、以下で定義される長さ
N の文字列
T を、「
S の中で先頭から
K 番目の 1 の塊を
K−1 番目の 1 の塊の直後まで移動した文字列」と定める
1≤i≤r
K−1
のとき
T
i
=S
i
r
K−1
+1≤i≤r
K−1
+(r
K
−l
K
)+1 のとき
T
i
= 1
r
K−1
+(r
K
−l
K
)+2≤i≤r
K
のとき
T
i
= 0
r
K
+1≤i≤N のとき
T
i
=S
i
制約
1≤N≤5×10
5
S は 0, 1 のみからなる長さ
N の文字列
2≤K
S には 1 の塊が
K 個以上含まれる
入力
入力は以下の形式で標準入力から与えられる。
N
K
S
出力
答えを出力せよ。
入力例 1
Copy
15 3
010011100011001
出力例 1
Copy
010011111000001
S には、
2 文字目から
2 文字目、
5 文字目から
7 文字目、
11 文字目から
12 文字目、
15 文字目から
15 文字目の
4 つの 1 の塊があります。
入力例 2
Copy
10 2
1011111111
出力例 2
Copy
1111111110
アルゴリズム
- N, K, Sを受け取る
- "0"と"1"の間に,を入れる
- ,区切りで分割してリスト形式にする
- 最初が1で始まる要素を数える
- 1の登場がK回になったら、その要素をa+1のところに入れる
- 表示形式に合わせて、結果を出力する。
回答
失敗作
N, K = map(int, input().split())
S = input()
l = S.replace("01", "0,1")
l = l.replace("10", "1,0")
l = list(map(str, l.split(",")))
key = 0
a= 0
for i in range(len(l)):
if l[i].startswith("1"):
key += 1
if key == K-1:
a = i
if key == K:
l.insert(a+1, l[i])
l.pop(i+1)
break
L= []
for i in range(len(l)):
L.append(int(l[i]))
from functools import reduce
LL = int(reduce(lambda x, y: x + y, [str(x) for x in L]))
print(LL)
参考
備考
- できそうで全然できなかった
- 正直なんでダメなのかはわからない。解説のアルゴリズムを見る限り、そこまでかけ離れているわけではない。細かいコードの違いと、余計な実装が多いからだと思う。もっとスマートにできるはず。
- そう考えると、手数の問題な気がする。現状手が少ないから、あの手この手で色々と盛り込んで全然スマートじゃないコードになっているはず。もっと手数を増やして、最適解をというのを見つける必要がある。
- あともちろんのこと、アルゴリズム（頭の中）が全然整理できていない。解説みたいに必要最低限のことを抽出する必要が、捨象大事！