Julia 言語で競技プログラミング

これはなに

julia で競技プログラミングをやるときの個人的 Tips 集です．
ときどき更新しようと思います．

間違ってるところがあったらビシッと指摘していただけると嬉しいです．
こうした方がいいよ！っていうところも是非．

環境はこんな感じです．AtCoderでも使える Version 1.4.0 です．

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.4.0 (2020-03-21)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |

julia> versioninfo()
Julia Version 1.4.0
Commit b8e9a9ecc6 (2020-03-21 16:36 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-8.0.1 (ORCJIT, skylake)

注意（特に他言語ユーザに向けて）

競プロやるなら，以下の点に注意しておけばまあ十分かなと思います．

• 1-based indexing．
• 基本的に，全ての処理は関数の中に入れる．入れないと遅い．
• グローバル変数には const つける．
• 関数は型安定じゃないと遅い．関数の返り値の型は１つに定まるように書く．
• mutable な構造体のメンバは型を指定する．
• 配列への要素の追加push!()は遅い．push!()したいならsizehint!()してから．
  • サイズがわかってるなら，サイズ分の配列を確保するほうが良いかも

入出力

基本的には readline() して parse() してます．

s = readline() # S（文字列）
n = parse(Int, readline()) # N
x, y = parse.(Int, split.(readline())) # X Y
a = parse.(Int, split.(readline()))  # A_1 A_2 ... A_N

# x_1 y_1
# x_2 y_2
# ......
# x_n y_n
x = zeros(Int, n)
y = zeros(Int, n)
for i in 1:n
    x[i], y[i] = parse.(Int, split(readline()))
end

基本はこんな感じだと思います．
一行に違う型が複数あるときは，split()して各要素ごとにparse()とかをしてあげる必要があります．
タイプするのが面倒くさいので，僕は適当にスニペットに登録してます．

各種データ構造

便利なパッケージ DataStructures.jl があります．
ドキュメント( https://juliacollections.github.io/DataStructures.jl/latest/ )を見ると......

This package implements a variety of data structures, including

• Deque (implemented with an unrolled linked list)
• CircularBuffer
• CircularDeque (based on a circular buffer)
• Stack
• Queue
• Priority Queue
• Fenwick Tree
• Accumulators and Counters (i.e. Multisets / Bags)
• Disjoint Sets
• Binary Heap
• Mutable Binary Heap
• Ordered Dicts and Sets
• RobinDict (implemented with Robin Hood Hashing)
• Dictionaries with Defaults
• Trie
• Linked List and Mutable Linked List
• Sorted Dict, Sorted Multi-Dict and Sorted Set
• DataStructures.IntSet
• SparseIntSet
• DiBitVector

よく使うデータ構造はたいてい抑えてありますね．
AtCoder でも使えるみたいです．

あるとうれしいやつ

なにか新しく実装したら追加するかもしれないです．

組み合わせ

逆元を使うやつです．
invmod() とかが既にあるので，コレだけでよいです．

function comb(n, a, m)
    ans = 1
    denom = 1
    for i in 0:a-1
        ans   = mod(ans*(n - i), m)
        denom = mod(denom*(i + 1), m)
    end
    ans = mod(ans*invmod(denom, m), m)
end

素因数分解

(素因数, 指数)のタプルの配列を返します．
$\sqrt{N}$ まで割れるやつで割っていく，よくある実装です．

function factor(n)
    m = Int(ceil(sqrt(n)))
    res = Tuple{Int, Int}[]
    sizehint!(res, m)
    for a in 2:m
        n % a != 0 && continue
        ex = 0
        while n % a == 0
            ex += 1
            n /= a
        end

        push!(res, (a, ex))
    end
    n != 1 && push!(res, (n, 1))

    return res
end