ZONeエナジー プログラミングコンテスト “HELLO SPACE” D - 宇宙人からのメッセージ【Python】
https://atcoder.jp/contests/zone2021/tasks/zone2021_d
AtCoder ProblemsでDifficulty: 719、Solve Probability: 37%でした。
Rごとに文字列を分けるとすると反転させた回数(右に何個Rがあるか)が偶数か奇数か2つのリストに分けて、奇数であればリストの順番と各要素(文字列)の順番を逆にし、2つのリストを連結しました。
連続する2つの文字列を削除する操作についてはdequeを使い解くことができました。
解説を見たところ反転の操作についてもdequeを使い、反転状態のときは先頭に文字列を追加していき、最終的に反転状態のときは全体を反転するというとても簡潔な解法でした。
from collections import deque S = input() even = [] odd = [] cur_s = [] R_count = 0 for s in S: if s != 'R': cur_s.append(s) else: R_count += 1 if R_count % 2 == 0: even.append(cur_s) else: odd.append(cur_s) cur_s = [] # 最終的に反転した回数が奇数の文字列のリストがodd,偶数の文字列のリストがeven if R_count % 2 == 0: even, odd = odd, even # Rに関する操作後の文字列を求める new_odd = [] for sl in odd[::-1]: new_odd.append(''.join(sl[::-1])) new_even = [] for sl in even: new_even.append(''.join(sl)) res = list(''.join(new_odd + new_even + cur_s)) # 同じ文字が2つ連続で並んでいたらその2文字を取り除く操作 # 一文字ずつ見ていき、片方のキューの右端ともう一方のキューの左端を比較して # 同じであれば取り除き、異なれば片方のキューにもう一方のキューの左端を追加する ans = deque() res = deque(res) ans.append('') while len(res) > 0: if ans[-1] == res[0]: ans.pop() res.popleft() else: ans.append(res.popleft()) print(''.join(ans))