はじめに
本記事は競技プログラミングにおいて解くのに困った問題について、なぜその解法に思い至るのか、どのような所でハマったか等のポイントをメモした、筆者の筆者による筆者のための備忘録となっております。読まれることを意識していないので文章がとっ散らかってます。
問題
問題はこちら。
概略
文字列Sを先頭から見ていき、空文字列$T$に対して以下の処理を行う。
- $S_i$ = 'R'のとき、 $T$を反転
- それ以外の時、 $T$の末尾に$S_i$を追加
最後に、$T_i = T_{i+1}$の時、それを消去することを、できなくなるまで行う(最終的な$T$の値は
この消去の順番に依らない)。
全ての操作が終了した時点での$T$を出力せよ。
提出解答
提出解答はこちら。
s = input()
n = len(s)
t_head = ['']*n
t_tail = ['']*n
head = 1
head_ind = 0
tail_ind = 0
for i in range(n):
if s[i] == 'R':
head *= -1
else:
if head == 1:
if head_ind > 0 and t_head[head_ind-1] == s[i]:
t_head[head_ind-1] = ''
head_ind -= 1
else:
t_head[head_ind] = s[i]
head_ind += 1
else:
if tail_ind > 0 and t_tail[tail_ind-1] == s[i]:
t_tail[tail_ind-1] = ''
tail_ind -= 1
else:
t_tail[tail_ind] = s[i]
tail_ind += 1
for i in range(min(len(t_head), len(t_tail))):
if t_head[i] == t_tail[i]:
t_tail[i] = ''
t_head[i] = ''
else:
break
ret = ''
ret_head = ''
ret_tail = ''
if head == 1:
t_tail.reverse()
for st in t_head:
ret_head += st
for st in t_tail:
ret_tail += st
ret = ret_tail + ret_head
else:
t_head.reverse()
for st in t_head:
ret_head += st
for st in t_tail:
ret_tail += st
ret = ret_head + ret_tail
print(ret)
かなり冗長になってしまった。反省。
初めに考えたこと
まず、問題文の操作をそのままやっていると絶対にTLEするため、文字を追加しながら文字列の消去を行う必要があります。幸い消去の順番に出力は依存しないため、こういったことが可能です。文字を追加する際にそのお隣さんが追加する文字と同じ文字だった場合は、文字を追加する代わりにそのお隣さんを消去してあげましょう。
次に反転操作ですが、これは典型として、反転しているか否かを保持する変数を作り、それに応じて追加する場所を先頭と末尾のどちらにするかを選択して要素を追加して、最後に反転する必要があれば反転をする、という考え方があります。これを使いましょう。
これで問題無いのですが、私は出力のための配列を2つ作り、先頭に追加する場合と末尾に追加する場合で別々の配列を使用し、最後に2つの配列を結合する、という手法を取りました。これでも問題は無いのですが、少し冗長です。また、文字列の消去の仕方も下手くそにやってしまったので、あまり良くありませんでした。
先述したやり方で全く問題ないのですが、それを実行するにあたっての問題点とその解決策について、次項でお話します。
計算量とdeque
前項で話した操作を実行するためには、以下の操作が$O(1)$程度で実行できる必要があります。
- 末尾への要素の追加
- 先頭への要素の追加
- 末尾の要素の消去
- 先頭の要素の消去
上記の4つの操作の内、末尾の追加・削除に関しては配列で問題なく処理できます(pythonの場合はappend, pop())。しかし先頭要素の追加・削除は、$O(n)$かかってしまうようです(pythonの場合はinsert, pop(i))。
これを解消するデータ構造としてdequeというものが存在します。これは配列と似たような構造をしていますが、先頭要素の追加・削除が$O(1)$で実行できる(pythonの場合はappendleft, popleft)という優れものです。これで問題は解決しました。
再提出解答
再提出解答はこちら。
from collections import deque
s = input()
n = len(s)
t = deque()
head = 1
for i in range(n):
if s[i] == 'R':
head *= -1
else:
if head == 1:
if len(t) > 0 and t[len(t)-1] == s[i]:
t.pop()
else:
t.append(s[i])
else:
if len(t) > 0 and t[0] == s[i]:
t.popleft()
else:
t.appendleft(s[i])
if head == -1:
t.reverse()
ret = ''
for v in t:
ret += v
print(ret)
コードがスッキリしました。
ちなみに配列で上記と同様の操作を実装してみたところ、しっかりTLEしました。こちらがその解答です。dequeのありがたみがわかります。
反省
- 変に難しいことをしようとして実装に馬鹿時間をかけてしまった。
- dequeはすごい。
- この調子で便利な標準ライブラリをインプットしていきたい。