Nim-ACL

Algorithm utilities

概要

algorithmutilsは旧来の総合algorithm utilityです。 singularなpermutation・combinationは互換APIとして維持し、 canonicalな実装をitertoolsへ委譲します。

import

import atcoder/extra/other/algorithmutils

permutationとcombination

for value in permutation(@[1, 2, 3]):
  discard value

for value in combination(@[1, 2, 3], 2):
  discard value

nth_element

var values = @[5, 1, 4, 2, 3]

values.nth_element(2)

doAssert values[2] == 3

custom comparatorと部分区間版も利用できます。

values.nth_element(nth, comparator)
values.nth_element(first, nth, last)
values.nth_element(first, nth, last, comparator)

copyとreverse

copy(source, slice, destination, destinationStart)
reverse(sequence, slice)

setUnion

昇順の2列の和集合を返します。

境界条件

計算量

API 計算量
permutation 出力件数 × O(n)
combination 出力件数 × O(r)
nth_element 平均的に線形時間
setUnion O(len(u) + len(v))

関連

検証