NimのlistsでABC344 E - Insert or Eraseを通したい
Nimには双方向リストが存在するが、微妙に痒い所に手が届かない。
とりあえず双方向リストだけ見ていくものとする。
typeの定義
code:nim
type
DoublyLinkedNodeObj*T = object ## A node of a doubly linked list.
##
## It consists of a value field, and pointers to next and prev.
prev* {.cursor.}: DoublyLinkedNodeT value*: T
DoublyLinkedNode*T = ref DoublyLinkedNodeObjT DoublyLinkedList*T = object ## A doubly linked list.
tail* {.cursor.}: DoublyLinkedNodeT こんな感じに定義されている。
今回の問題でやりたいこと
クエリ1:あるノードの次に、新しいノードを追加したい
クエリ2:リストから、あるノードを消去したい
これのクエリ2にあたるものは既に実装されているので、クエリ1の方をなんとかしたい。
クエリによってDoublyLinkedListのheadやtailが変化しかねないので、関数を作成する場合はDoublyLinkedListと二つのDoublyLinkedNodeを引数にとるべきである。
removeでは、headやtailと一致しているかとかを見ているので、そんな感じの実装にするとよさそう。
code:nim
proc insert*T(L: var DoublyLinkedListT, a,b: DoublyLinkedNodeT)= if L.tail == a:
L.tail = b
a.next = b
b.prev = a
else:
a.next.prev = b
b.next = a.next
a.next = b
b.prev = a
これを書いておくと、aの後にbの挿入ができて、便利。
code:nim
import lists
var N = ii()
var list = initDoublyLinkedListint() var A = lii(N)
var tonode = initTable[int,DoublyLinkedNodeint]() for i in range(N):
var tmp = newDoublyLinkedNodeint(Ai) list.add(tmp)
proc insert*T(L: var DoublyLinkedListT, a,b: DoublyLinkedNodeT)= if L.tail == a:
L.tail = b
a.next = b
b.prev = a
else:
a.next.prev = b
b.next = a.next
a.next = b
b.prev = a
var Q = ii()
for i in range(Q):
var t = ii()
if t == 1:
var x,y = ii()
var tmp = newDoublyLinkedNodeint(y) else:
var x = ii()
tonode.del(x)
echo list.toseq().join(" ")
ついでに手前への挿入も実装しておこう。
code:nim
proc insertPrev*T(L: var DoublyLinkedListT, a,b: DoublyLinkedNodeT)= if L.head == a:
L.head = b
a.prev = b
b.next = a
else:
a.prev.next = b
b.prev = a.prev
a.prev = b
b.next = a
以下使用例
code:ABC237.nim
import lists
proc insertPrev*T(L: var DoublyLinkedListT, a,b: DoublyLinkedNodeT)= if L.head == a:
L.head = b
a.prev = b
b.next = a
else:
a.prev.next = b
b.prev = a.prev
a.prev = b
b.next = a
proc insert*T(L: var DoublyLinkedListT, a,b: DoublyLinkedNodeT)= if L.tail == a:
L.tail = b
a.next = b
b.prev = a
else:
a.next.prev = b
b.next = a.next
a.next = b
b.prev = a
var N = ii()
var S = si()
var list = initDoublyLinkedListint() var bef = newDoublyLinkedNodeint(0) list.add(bef)
for i in range(N):
var tmp = newDoublyLinkedNodeint(i+1) list.insert(bef,tmp)
else:
list.insertPrev(bef,tmp)
bef = tmp
echo list.toseq().join(" ")
便利