ABC237D - LR insertion

解法1

考え方

逆から考えれば，両端にしか文字を追加せずに済むので，dequeをつかえば良い．
Editorial - AtCoder Beginner Contest 237

回答例

collections --- コンテナデータ型 — Python 3.10.0b2 ドキュメント

from collections import deque
N = int(input())
S = input()

q = deque([N])
for s in reversed(S):
  N -= 1
  if s == 'L':
    q.append(N)
  else:
    q.appendleft(N)
 
print(*q)

解法2

Editorial - AtCoder Beginner Contest 237

解法3

考え方

$0,1,...,N$の左右の数字を記録しておけば，最後に復元できる．
めんどくさい方法で解いてしまった．

回答例

N = int(input())
S = input()
pos_right = [-1] * (N + 1)
pos_left = [-1] * (N + 1)
for i, s in enumerate(S):
  if s == 'L':
    if pos_left[i] > -1:
      pos_right[pos_left[i]] = i + 1       
    pos_right[i + 1] = i
    pos_left[i], pos_left[i + 1] = i + 1, pos_left[i]

  else:
    if pos_right[i] > -1:
      pos_left[pos_right[i]] = i + 1
    pos_right[i], pos_right[i + 1] = i + 1, pos_right[i]
    pos_left[i + 1] = i
    
for i, x in enumerate(pos_left):
  if x== -1:
    cur = i
    break
    
ans = []
for _ in range(N + 1):
  ans.append(cur)
  cur = pos_right[cur]
    
print(*ans)