D - LR insertion Editorial by kyopro_friends
公式解説では後ろから解いていますが、前から解くこともできます。
\(i\) 番目の操作が終わった時点で \(i\) より左側の要素からなる数列を \(L\)、右側の要素からなる数列を \(R\) とします。
例えばサンプル \(1\) であれば
- 初期状態では、\(A=(0)\) であり、\(L=(),R=()\)
- \(i=1\) のとき、\(s_1=\)
L
なので \(A=(1,0)\) であり、\(L=(),R=(0)\) - \(i=2\) のとき、\(s_2=\)
R
なので \(A=(1,2,0)\) であり、\(L=(1),R=(0)\) - \(i=3\) のとき、\(s_3=\)
R
なので \(A=(1,2,3,0)\) であり、\(L=(1,2),R=(0)\) - \(i=4\) のとき、\(s_4=\)
L
なので \(A=(1,2,4,3,0)\) であり、\(L=(1,2),R=(3,0)\) - \(i=5\) のとき、\(s_5=\)
R
なので \(A=(1,2,4,5,3,0)\) であり、\(L=(1,2,4),R=(3,0)\)
というようになります。一連の操作をよく観察すると、\(s_i=\)L
のとき \(R\) の先頭に \(i-1\) を挿入し、\(s_i=\)R
のとき \(L\) の末尾に \(i-1\) を挿入していることがわかります。
したがって、「両端 queue を使う」「\(R\) を reverse した状態で持つ」などにより、操作は \(O(1)\) で行えます。
実装例(Python)
L=[]
R=[]
N=int(input())
S=input()
for i,c in enumerate(S):
if c=='L': R.append(i)
else: L.append(i)
print(*(L+[N]+R[::-1]))
公式解説では「真ん中」を持っていたのに対し、こちらの解法では「両端」を持っていたとみなすことができます。
posted:
last update: