Git Product home page Git Product logo

ac-library.cr's Introduction

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]

ac-library.cr's People

Contributors

hakatashi avatar ngng628 avatar universato avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.