Git Product home page Git Product logo

ac-library.cr's Introduction

ac-library.cr Run test and verifier

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.

ModInt.cr (<atcoder/modint>)

  • 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

FenwickTree.cr (<atcoder/fenwicktree>)

  • 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.cr (<atcoder/segtree>)

  • segtree<S, op, e> seg(v) => AtCoder::SegTree(S).new(v, &op?)

    単位元は暗黙的にnilで定義されるため使用する際に定義する必要はありません。逆に言えばモノイドの (単位元以外の) 元にnilを含めることはできません。 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) => Unimplemented
    • .max_left<f>(r) => Unimplemented

LazySegTree.cr (<atcoder/lazysegtree>)

  • lazy_segtree<S, op, e, F, mapping, composition, id> seg(v) => AtCoder::LazySegTree(S, F).new(v, op, mapping, composition)

    単位元は暗黙的にnilで定義されるため使用する際に定義する必要はありません。逆に言えばモノイドの (単位元以外の) 元にnilを含めることはできません。 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.

    また、恒等写像は暗黙的にnilで定義されるため使用する際に定義する必要はありません。逆に言えばFの (恒等写像以外の) 元にnilを含めることはできません。 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) => Unimplemented
    • .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) => Unimplemented
    • .max_left<f>(r) => Unimplemented

DSU.cr (<atcoder/dsu>)

  • 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.

MaxFlow.cr (<atcoder/maxflow>)

  • 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.cr (<atcoder/scc>)

  • 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

TwoSat.cr (<atcoder/twosat>)

  • 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

Math.cr (<atcoder/math>)

  • 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)

PriorityQueue.cr (not in ACL)

  • 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.

    • #size

      Returns size of the queue

Prime.cr (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 universato avatar

Stargazers

Neos21 avatar Hsiang Shen, Chiu avatar Reza Eskandari avatar Vlad Zarakovsky avatar Taupiqueur avatar  avatar Keany Vy KHUN avatar Caspian Baska avatar Kai Devrim avatar Second Datke avatar sakuragi avatar Yu-Cheng Huang avatar omppye avatar Sora Morimoto avatar 9sako6 avatar  avatar Naoya Niwa avatar universato avatar Volodymyr  avatar Vitalii Elenhaupt avatar Alexander ADAM avatar Sergey Fedorov avatar Anton Maminov avatar Kato, H. avatar Dushyant Singh avatar  avatar fabon avatar Hiroyuki Katsura avatar

Watchers

Chris DiBona avatar James Cloos avatar Koki Takahashi 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.