Skip to content

hakatashi/ac-library.cr

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

ac-library.cr Run test and verifier Coverage

This is not an officially supported Google product.

ac-library.cr is a Crystal port of ac-library.

This library aims to provide the almost-equivalent (and additional) functionality with ac-library but in the manner of Crystal.

Installation

Add the following code to your project's shard.yml.

dependencies:
  atcoder:
    github: hakatashi/ac-library.cr
    branch: master

Usage

require "atcoder" # load all libraries
require "atcoder/fenwick_tree" # load FenwickTree
  • modint => Unimplemented

  • modint998244353 => AtCoder::ModInt998244353

  • modint1000000007 => AtCoder::ModInt1000000007

    alias Mint = AtCoder::ModInt1000000007
    Mint.new(30_i64) // Mint.new(7_i64) #=> 285714292
  • static_modint => AtCoder.static_modint

    AtCoder.static_modint(ModInt101, 101_i64)
    alias Mint = AtCoder::ModInt101
    Mint.new(80_i64) + Mint.new(90_i64) #=> 89
  • dynamic_modint => Unimplemented

  • fenwick_tree<T> fw(n) => AtCoder::FenwickTree(T).new(n)

  • fenwick_tree<T> fw(array) => AtCoder::FenwickTree(T).new(array)

    tree = AtCoder::FenwickTree(Int64).new(10)
    tree.add(3, 10)
    tree.add(5, 20)
    tree[3..5] #=> 30
    tree[3...5] #=> 10
    • .add(p, x) => #add(p, x)
    • .sum(l, r) => #[](l...r)
  • segtree<S, op, e> seg(v) => AtCoder::SegTree(S).new(v, &op?)

    The identity element will be implicitly defined as nil, so you don't have to manually define it. In the other words, you cannot include nil into an element of the monoid.

    tree = AtCoder::SegTree.new((0...100).to_a) {|a, b| [a, b].min}
    tree[10...50] #=> 10
    • .set(p, x) => #[]=(p, x)
    • .get(p) => #[](p)
    • .prod(l, r) => #[](l...r)
    • .all_prod() => #all_prod
    • .max_right<f>(l) => #max_right(l, e = nil, &f)
      • If the identity element is not given, it computes as f(e: nil) = true.
    • .min_left<f>(r) => #min_left(r, e = nil, &f)
      • If the identity element is not given, it computes as f(e: nil) = true.
  • lazy_segtree<S, op, e, F, mapping, composition, id> seg(v) => AtCoder::LazySegTree(S, F).new(v, op, mapping, composition)

    The identity element will be implicitly defined as nil, so you don't have to manually define it. In the other words, you cannot include nil into an element of the monoid.

    Similarly, the identity map of F will be implicitly defined as nil, so you don't have to manually define it. In the other words, you cannot include nil into an element of the set F.

    op = ->(a : Int32, b : Int32) { [a, b].min }
    mapping = ->(f : Int32, x : Int32) { f }
    composition = ->(a : Int32, b : Int32) { a }
    tree = AtCoder::LazySegTree(Int32, Int32).new((0...100).to_a, op, mapping, composition)
    tree[10...50] #=> 10
    tree[20...60] = 0
    tree[50...80] #=> 0
    • .set(p, x) => #set(p, x)
    • .get(p) => #[](p)
    • .prod(l, r) => #[](l...r)
    • .all_prod() => #all_prod
    • .apply(p, f) => #[]=(p, f)
    • .apply(l, r, f) => #[]=(l...r, f)
    • .max_right<f>(l) => #max_right(l, e = nil, &f)
      • If the identity element is not given, it computes as f(e: nil) = true.
    • .min_left<f>(r) => #min_left(r, e = nil, &f)
      • If the identity element is not given, it computes as f(e: nil) = true.
  • suffix_array(s) => AtCoder::String.suffix_array(s)
  • lcp_array(s) => AtCoder::String.lcp_array(s)
  • z_algorithm(s) => AtCoder::String.z_algorithm(s)
  • dsu(n) => AtCoder::DSU.new(n)

    dsu = AtCoder::DSU.new(10)
    dsu.merge(0, 2)
    dsu.merge(4, 2)
    dsu.same?(0, 4) #=> true
    dsu.size(4) #=> 3
    • .merge(a, b) => #merge(a, b)

    • .same(a, b) => #same?(a, b)

    • .leader(a) => #leader(a)

    • .size() => #size

    • .groups() => #groups

      • This method returns set instead of list.
  • mf_graph<Cap> graph(n) => AtCoder::MaxFlow.new(n)

    Cap is always Int64.

    mf = AtCoder::MaxFlow.new(3)
    mf.add_edge(0, 1, 3)
    mf.add_edge(1, 2, 1)
    mf.add_edge(0, 2, 2)
    mf.flow(0, 2) #=> 3
    • .add_edge(from, to, cap) => #add_edge(from, to, cap)
    • .flow(s, t) => #flow(s, t)
    • .min_cut(s) => Unimplemented
    • .get_edge(i) => Unimplemented
    • .edges() => Unimplemented
    • .change_edge(i, new_cap, new_flow) => Unimplemented
  • scc_graph graph(n) => AtCoder::SCC.new(n)

    scc = AtCoder::SCC.new(3_i64)
    scc.add_edge(0, 1)
    scc.add_edge(1, 0)
    scc.add_edge(2, 0)
    scc.scc #=> [Set{2}, Set{0, 1}]
    • .add_edge(from, to) => #add_edge(from, to)
    • .scc() => #scc
  • two_sat graph(n) => AtCoder::SCC.new(n)

    twosat = AtCoder::TwoSat.new(2_i64)
    twosat.add_clause(0, true, 1, false)
    twosat.add_clause(1, true, 0, false)
    twosat.add_clause(0, false, 1, false)
    twosat.satisfiable? #=> true
    twosat.answer #=> [false, false]
    • .add_clause(i, f, j, g) => #add_clause(i, f, j, g)

    • .satisfiable() => #satisfiable?

    • .answer() => #answer

      This method will raise if it's not satisfiable

  • pow_mod(x, n, m) => AtCoder::Math.pow_mod(x, n, m)
  • inv_mod(x, m) => AtCoder::Math.inv_mod(x, m)
  • crt(r, m) => AtCoder::Math.crt(r, m)
  • floor_sum => AtCoder::Math.floor_sum(n, m, a, b)
  • convolution(a, b) => AtCoder::Convolution.convolution(a, b)

    a = [AtCoder::ModInt998244353.new(1_i64)] * 3
    AtCoder::Convolution.convolution(a, a) #=> [1, 2, 3, 2, 1]
  • convolution_ll(a, b) => AtCoder::Convolution.convolution_ll(a, b)

    a = [1_000_000_000_i64]
    AtCoder::Convolution.convolution_ll(a, a) #=> [1000000000000000000]
  • mcf_graph graph(n) => AtCoder::MinCostFlow.new(n)

    flow = AtCoder::MinCostFlow.new(5)
    flow.add_edge(0, 1, 30, 3)
    flow.add_edge(0, 2, 60, 9)
    flow.add_edge(1, 2, 40, 5)
    flow.add_edge(1, 3, 50, 7)
    flow.add_edge(2, 3, 20, 8)
    flow.add_edge(2, 4, 50, 6)
    flow.add_edge(3, 4, 60, 7)
    flow.flow(0, 4, 70) #=> {70, 1080}
    • .add_edge(from, to, cap, cost) => #add_edge(from, to, cap, cost)
    • .flow(s, t) => #flow(s, t)
    • .flow(s, t, flow_limit) => #flow(s, t, flow_limit)
    • .slope(s, t) => #slope(s, t)
    • .slope(s, t, flow_limit) => #slope(s, t, flow_limit)
    • .get_edge(i) => Unimplemented
    • .edges() => Unimplemented
  • AtCoder::PriorityQueue(T).new

    q = AtCoder::PriorityQueue(Int64).new
    q << 1_i64
    q << 3_i64
    q << 2_i64
    q.pop #=> 3
    q.pop #=> 2
    q.pop #=> 1
    • #<<(v : T)

      Push value into the queue.

    • #pop

      Pop value from the queue.

    • #each

      Yields each item in the queue in comparator's order.

      It pre-calculates in O(NlogN) to enumerate without destroying the heap. Note, however, that #first works for O(1).

      q = AtCoder::PriorityQueue.new(1..n)
      
      # O(n log(n))
      q.each do |x|
        break
      end
      
      # O(n log(n) + n) = O(n log(n))
      q.each do |x|
        # something to do in O(1)
      end
      
      # O(1)
      q.first # => n
    • #size

      Returns size of the queue

    • #empty?

      Returns true if the queue is empty.

atcoder/prime (not in ACL)

  • AtCoder::Prime (module)

    Implements Ruby's Prime library.

    AtCoder::Prime.first(7) # => [2, 3, 5, 7, 11, 13, 17]