AtCoderでJuliaを使う

背景

今まで、C++でAtCoderに参加していたのですが、普段使わないC++は期間が開くと忘れてしまうのでJuliaに乗り換えようと思ったのです。
以下では試しにABC186の問題を解いてみようと思います。ここでは、コードの説明を中心に行うので、アルゴリズムなどの解説は公式の解説を見てください。

A問題

この問題はNをWで割ればいいので簡単ですが入出力が少し面倒です。

	N ,W = readline |> split .|> x -> parse(Int16,x)
	println(N)

このように書いておくと可読性が上がって良いと思います。
以下のように関数化しておくことも良いでしょう。

	function main()
		N ,W = readline() |> split .|> x -> parse(Int16,x)
		println(N÷W)
	end
	main()

B問題

次の問題はマスに乗っているブロック数を表す配列Aの最小値を求め、
$$
総ブロック数-最小値×マスの数
$$
を計算すればいい。これを直感的に書くと

function main()
    H ,W= readline() |> split .|> x -> parse(Int,x)
    A=Array{Int,2}(undef,H,W)
    for i in 1:H
        A[i,:]= readline() |> split .|> x -> parse(Int,x)
    end
    Amin=min(A...)
    Asum=sum(A)
    println(Asum-Amin*H*W)
end
main()

のようになるだろう。しかし、ここで問題がある。JuliaはColumn-major orderなので、

function main()
    H ,W= readline() |> split .|> x -> parse(Int,x)
    A=Array{Int,2}(undef,W,H)
    for i in 1:H
        A[:,i]= readline() |> split .|> x -> parse(Int,x)
    end
    Amin=min(A...)
    Asum=sum(A)
    println(Asum-Amin*H*W)
end
main()

のほうが速い。実際、AtCoderで計測したところ、前者が381 msのところ、後者は351 msになっている。つまり、10 % 程速くなっているので、D,E,F問題では注意が必要になるかもしれない。

C問題

これは、forで愚直に全部調べるのがいいでしょう。Juliaにはstring関数のキーワードにbaseというものがあり、何進数ので表すかが選べます。これを使うと以下のようになります。

function main()
    N=readline() |> x -> parse(Int,x)
    count=0
    for i in 1:N
        if '7' in string(i, base=8) || '7' in string(i, base=10)
            count+=1
        end
    end
    println(N-count)
end
main()

ここで1つ大事なことは1行目でsplitが抜けていることです。これをしないとNが1成分の配列となり、for i in 1:Nの所でerrorが出ます。

D問題

この問題は、配列Aをsortしておくことで絶対値をはず事が重要です。sortした後の配列を$\tilde{A}$(昇順)とすると、

$$\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} \left| A_i-A_j \right| = \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} \left( \tilde{A}_j - \tilde{A}_i \right)_.$$

内側の$\sum$を実行すると、

$$\sum_{i=1}^{N-1} \left( \sum_{j=i+1}^{N}\tilde{A}_j - \left( N -i\right)\tilde{A}_i \right)_.$$

これを実際に実装してみます。

function main()
    N=readline() |> x -> parse(Int,x)
    A=Array{Int,1}(undef,N)
    A=readline() |> split .|> x -> parse(Int,x)
    sort!(A) # 小さい順
    out=0
    B=0
    for j in N:-1:2
        B+=A[j]
        out+=B-(N-j+1)*A[j-1]
    end
    println(out)
end
main()

ここで、少し工夫を加えて$\sum_{j=i+1}^{N}\tilde{A}_j$ の部分を変数$B$と定義し、for文をNから1に向けて回しています。

終わりに

今回ABC186のD問題までJuliaで解いてみました。これは僕が今までE問題以上をコンテスト中に解けたことがないためです。これから、

• 入出力はreadline() |> x -> parse(Int,x)のようにすると読みやすく型の指定もしやすい。
• JuliaはC++などよりメモリの消費を抑えにくいがD問題までなら意識せずに書いても大丈夫

と分かりました。しかし、メモリを多く使うグラフ問題は今回のコンテストに入っていないです。

次回はグラフ問題を実装しようと思います。