D - LR insertion 解説 by cirno3153
この問題は、双方向リストを用いることで直接解くことができます。
双方向リストは、任意の位置の挿入と削除が \(O(1)\) 、検索が \(O(\rm{distance})\) かかるデータ構造です。
双方向リストのイテレータを用意し、初めは末尾の位置にいるものとします。 また、イテレータに対して挿入操作を行った場合、見ている位置の直前に値が挿入されるものとします。 与えられる操作を次のように実行することで、正しい答えを得ることができます。
- \(s_i\) が
L
ならば、イテレータを一つ戻し、値を挿入する。 - \(s_i\) が
R
ならば、値を挿入する。
C++による実装例
#include<iostream>
#include<list>
#include<string>
int main() {
int N;
std::string S;
std::cin >> N >> S;
std::list<int> A{0};
std::list<int>::iterator iter = A.end();
for (int i = 0;i < N;++ i) {
if (S[i] == 'L') -- iter;
A.insert(iter, i + 1);
}
for (int i : A) std::cout << i << ' ';
return 0;
}
Javaによる実装例
import java.util.*;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(System.in)) {
int N = sc.nextInt();
char[] S = sc.next().toCharArray();
LinkedList<Integer> list = new LinkedList<>();
list.add(0);
ListIterator<Integer> iter = list.listIterator();
iter.next();
for (int i = 0;i < N;++ i) {
if (S[i] == 'L') iter.previous();
iter.add(i + 1);
}
for (int i : list) System.out.print(i + " ");
}
}
}
投稿日時:
最終更新: