ABC-047C - 一次元リバーシ / 1D Reversi をpythonで解く

atcoder.jp

リバーシにおいて同じ色の1個の石も2個の石も等価なので，まずは同じ色の並んだ部分を1個の石に置き換えると，あとは1個ずつひっくり返していくしかないのでその長さ-1が答えとなる．

解法1 np.diffを使う

import numpy as np

S=input()
S=np.array([1 if s=='B' else 0 for s in S])

answer = np.abs(np.diff(S)).sum()
print(answer)

AC @ 334ms

変化点を見つけるためには差分系列を取れば良い．01からなるndarrayに変更しておけば，np.diffで差分をとって，その絶対値の和をとれば良い．

経過時間はimport numpyに時間がかかっている．

解法2 itertools.groupby

from itertools import groupby

S=input()
answer = -1
for _ in groupby(S):
  answer+=1

print(answer)

AC @ 32ms itertools内のgroupbyは値が切り替わるたびに値を送出するiterater．sort済みの配列に対して使われることが多いが，このように単に連続する値をグループ化したいときにも使える．iteratorなので回しきらないと全体数がわからないのがネックだが，逆に複雑な処理が必要な場合も有効かも．

for文のところは，リスト内包表記でも書けてちょっと早くなる（AC @28ms）

from itertools import groupby

S=input()
answer = sum([1 for _ in groupby(S)]) -1

print(answer)

解法3 実直に

S=input()

answer=0
prev=S[0]
for s in S:
  if s!=prev:
    answer+=1
  prev=s

print(answer)

AC @33ms いろが変わるたびにanswerを+1する．

個人的にはnumpyの解法が好き．