AtCoder
Julia
競技プログラミング
JuliaDay 14

Juliaで競技プログラミング(AtCoder)やるときのTips

More than 1 year has passed since last update.

はじめに

プログラミング言語覚え始めの頃に競技プログラミングできるサイトで書く練習をしたりします。

Juliaを初めてまだまだ手に馴染むところまでいけていないため、Julia(0.5.0)が使えるAtCoderさんで練習してみました。

その時に使った&使いそうなコードのTipsをまとめます。
(アルゴリズム系の話はしません)

他にもオススメの小技等アレば是非教えていただきたいです:bow:

標準入出力

これ抜きでは語れませんね。

標準入力

readline()

ファイルを読み込む時に使っているやつです。
デフォルト引数でSTDINというIO型のオブジェクトが渡され標準入力の値を読みます。

標準出力

julia> print("hoge")
hoge

改行する時は

julia> println("hoge")
hoge

変数や式も埋め込めます。

julia> x = 3
julia> print("$x $(x * 3)")
3 9

入力データの処理

標準入力で受け取ったものを操作しやすいように落とし込みます。

区切り文字での分割

julia> split("1 2 3")
3-element Array{SubString{String},1}:
 "1"
 "2"
 "3"

デフォルトだとスペースで分割して配列にします。

変換

配列にしたら数値はInt型で扱いたいですね。

julia> parse("1")
1
julia> parse.(split("1 2 3"))
3-element Array{Int64,1}:
 1
 2
 3

Juliaでは関数名のお尻に.(ドット)をつけることで

julia> map(parse, split("1 2 3"))
3-element Array{Int64,1}:
 1
 2
 3

と等価になります。
どうでしょう。この辺り、Julia使いたくなりませんか??

*実際、parse(str::AbstractString)は文字列中の式を評価するもののため、parse(Int, "1")が正しいですが、文字列が数値のみの場合、挙動は一緒になるのでparseでいきます。

julia> parse("x = 3")
:(x = 3)
julia> x
3

配列の操作

配列の生成

Python同様、リスト内記法が使えます

julia> [x for x = 1:10 if x % 3 == 0]
3-element Array{Int64,1}:
 3
 6
 9

アルファベットも

julia> [c for c = 'A':'Z']
26-element Array{Char,1}:
 'A'
 'B'
 'C'
  ⋮ 

要素毎の計算

関数のときの.のように演算にも使えます。

julia> x = [i for i = 1:3]
julia> x .^ 2
3-element Array{Int64,1}:
 1
 4
 9

無名関数

これもすごくシンプル。
かつ.も使えます。

julia> (x->2x+3).([n for n = 1:3])
3-element Array{Int64,1}:
 5
 7
 9

でも単純な演算だけならこっちの方がいい...

julia> [n for n = 1:3] * 2 + 3
3-element Array{Int64,1}:
 5
 7
 9

行列計算

行列の計算も簡単にできます。

julia> A = [n for n = 1:3]
julia> A * A'
3×3 Array{Int64,2}:
 1  2  3
 2  4  6
 3  6  9

'は転置です。

*で通常の乗算をしたり、行列計算ができるのは多重ディスパッチの恩恵ですね。

入力からそのまま行列へ

入力が1行でシェイプが決まっている場合

julia> input = readline() # "1 2 3 4 5 5"
julia> reshape(parse.(split(input)), 2, 3)
2×3 Array{Int64,2}:
 1  3  5
 2  4  6

入力毎に列が来る場合

(行が来る場合は転置すればいい)

julia> inputs = [readline() for _=1:3] # 1 2; 3 4; 5 6;
julia> hcat((s->parse.(s)).(split.(inputs))...)
2×3 Array{Int64,2}:
 1  3  5
 2  4  6

条件

まとめて条件チェック

julia> all(iseven.([n for n = 2:2:10]))
true

一つだけでもあれば

julia> any(iseven.([n for n = 1:10]))
true

何個正しいか

julia> count(iseven.([n for n = 1:10]))
5

それぞれ一致するか

julia> c = rand(1:3, 3)
3-element Array{Int64,1}:
 3
 3
 1
julia> c = rand(1:3, 3)
3-element Array{Int64,1}:
 3
 2
 3
julia> c .== d
3-element BitArray{1}:
  true
 false
 false

文字

文字の羅列

julia> "hoge" ^ 20
"hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge"

文字の数

julia> count(c->c=='g', "hogefuga")
2

文字を含むか

辞書

数え上げ

get使うのが便利なのかな...?

julia> counts = Dict{Char, Int}()
julia> for c in rand('A':'Z', 1000)
         counts[c] = get(counts, c, 0) + 1
       end
julia> counts
Dict{Char,Int64} with 26 entries:
  'B' => 37
  'M' => 38
  'I' => 38
   ⋮ 

おわりに

行列の演算、強力な標準ライブラリ、要素ごとへの関数の適用などが便利で使うきっかけになりうるのではないでしょうか。

注意

JuliaはJITコンパイラで動作します。
関数を定義した時、その関数がコンパイルされます。
つまり関数化しないと遅いです。

print("$(parse(readline()) + sum(parse.(split(readline())))) $(readline())")
f(a, b, c) = print("$(parse(a) + sum(parse.(split(b)))) $(c)")

f(readline(), readline(), readline())

これだけでも1000ms→500msに改善しました。

参考