JuliaでPAST第3回に参戦した話 - はるすえすしーのぶろぐ

こんにちは。まぁじです。無料だったのでPAST第3回受験しました。
結果は64点・中級(A~I)でした。
f:id:halss:20200614182927p:plain

PAST第3回の過去問へのリンクは以下です。
atcoder.jp

解けた問題と終了後に解いた問題の解法を書いていこうと思います。
ちなみに入力は以下です。以降のコードでは省略します。

parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

A - ケース・センシティブ
B - ダイナミック・スコアリング
C - 等比数列
D - 電光掲示板
E - スプリンクラー
F - 回文行列
G - グリッド金移動
H - ハードル走
I - 行列操作
解けなかった問題
あとがき

A - ケース・センシティブ

"case-insentive"とtypoして1WAかましました。前にもdangerousで1WAしたことがあるので気をつけたいです。
Submission #14214322 - 第三回アルゴリズム実技検定

function main()
    s::String,t::String=readline(),readline()
    if s==t
        println("same")
    elseif lowercase(s)==lowercase(t)
        println("case-insensitive")
    else
        println("different")
    end
end
main()

B - ダイナミック・スコアリング

zeros(Int,n,m)はn x mの行列を生成するので、要素にアクセスする場合は[行][列] ではなく[行,列] という風に記述する必要があります。
Submission #14214861 - 第三回アルゴリズム実技検定

function main()
    n::Int,m::Int,q::Int=parseMap(split(readline()))
    point::Vector{Int}=fill(n,m)
    ac::Array{Int,2}=zeros(Int,n,m)
    for i in 1:q
        s::Vector{Int}=parseMap(split(readline()))
        if s[1]==1
            println(sum([point[j]*ac[s[2],j] for j in 1:m]))
        else
            ac[s[2],s[3]]=true
            point[s[3]]-=1
        end
    end
end
main()

C - 等比数列

等比R=1の時のみ枝刈りしてあげればNがどれだけ大きくても10^9を超えるのでそのまま実装すればいいです。
Submission #14216828 - 第三回アルゴリズム実技検定

function main()
    a::Int,r::Int,n::Int=parseMap(split(readline()))
    if r==1
        println(a)
    else
        ans::Int128=a
        for i in 2:n
            ans*=r
            if ans>10^9
                println("large")
                return
            end
        end
        println(ans)
    end
end
main()

D - 電光掲示板

4x5文字を横に連結して答えのDictを作りました。正攻法ではないと思いますが、割と楽しい問題でした。
Submission #14280211 - 第三回アルゴリズム実技検定

function main()
    n::Int=parseInt(readline())
    s::Vector{String}=[readline() for i in 1:5]
    answer=Dict{String,Int}([".###.#.#.#.#.#.#.###"=>0,"..#..##...#...#..###"=>1,".###...#.###.#...###"=>2,".###...#.###...#.###"=>3,".#.#.#.#.###...#...#"=>4,".###.#...###...#.###"=>5,".###.#...###.#.#.###"=>6,".###...#...#...#...#"=>7,".###.#.#.###.#.#.###"=>8,".###.#.#.###...#.###"=>9])
    for i in 1:n
        print(answer[join([s[j][i*4-3:i*4] for j in 1:5])])
    end
end
main()

E - スプリンクラー

隣接リストを用意してクエリ通りに色を変えていくだけです。
Submission #14217544 - 第三回アルゴリズム実技検定

function main()
    n::Int,m::Int,q::Int=parseMap(split(readline()))
    rinsetsu::Vector{Vector{Int}}=[[] for i in 1:n]
    for i in 1:m
        u::Int,v::Int=parseMap(split(readline()))
        push!(rinsetsu[u],v)
        push!(rinsetsu[v],u)
    end
    color::Vector{Int}=parseMap(split(readline()))
    for i in 1:q
        s::Vector{Int}=parseMap(split(readline()))
        println(color[s[2]])
        if s[1]==1
            for j in rinsetsu[s[2]]
                color[j]=color[s[2]]
            end
        else
            color[s[2]]=s[3]
        end
    end
end
main()

F - 回文行列

１～n÷2行目について各行のどれかの文字がn-i+1行目にあれば答えに追加、なければ-1とします。制約がN≦500と優しいです。
Submission #14269550 - 第三回アルゴリズム実技検定

function main()
    n::Int=parseInt(readline())
    a::Vector{Vector{String}}=[split(readline(),"") for i in 1:n]
    mae::Vector{String}=[]
    for i in 1:n÷2
        flag::Bool=true
        for j in 1:n
            if a[i][j] in a[n-i+1]
                push!(mae,a[i][j])
                flag=false
                break
            end
        end
        if flag
            println(-1)
            return
        end
    end
    s=join(mae)
    if n%2==1
        println(s*string(a[n÷2+1][1])*s[end:-1:1])
    else
        println(s*s[end:-1:1])
    end
end
main()

G - グリッド金移動

−201 ≤ x ≤ 201, −201 ≤ y ≤ 201の配列を用意して~~なぜか~~バグらせたので−210 ≤ x ≤ 210, −210 ≤ y ≤ 210のマップを用意してます。BFSでゴールまでの最短経路を求めてその手数を出力すれば終わりです。300点くらい？
DataStructuresのQueueは初めて使いました。
Submission #14269627 - 第三回アルゴリズム実技検定

using DataStructures

function main()
    n::Int,x::Int,y::Int=parseMap(split(readline()))
    INF::Int,NO::Int=2<<33,2<<34
    MAP::Vector{Vector{Int}}=[[INF for i in -210:210] for j in -210:210]
    MAP[0+211][0+211]=0
    for i in 1:n
        xi::Int,yi::Int=parseMap(split(readline()))
        MAP[yi+211][xi+211]=NO
    end

    arr::Queue{Tuple{Int,Int}}=Queue{Tuple{Int,Int}}()
    enqueue!(arr,(0,0))
    while !isempty(arr)
        nx::Int,ny::Int=dequeue!(arr)
        if nx==x && ny==y
            break
        end
        for (i,j) in [(nx+1,ny+1),(nx,ny+1),(nx-1,ny+1),(nx+1,ny),(nx-1,ny),(nx,ny-1)]
            if -211<i<211 && -211<j<211 && MAP[j+211][i+211]<NO && MAP[j+211][i+211]>MAP[ny+211][nx+211]+1
                MAP[j+211][i+211]=MAP[ny+211][nx+211]+1
                enqueue!(arr,(i,j))
            end
        end
    end
    if MAP[y+211][x+211]==INF
        println(-1)
    else
        println(MAP[y+211][x+211])
    end
end
main()

H - ハードル走

ゴールのみ飛び越したときにDPテーブルを更新することだけ気を付けておけば、配るDPでできると思います。難しい300点くらい？
Submission #14270091 - 第三回アルゴリズム実技検定

function main()
    n::Int,l::Int=parseMap(split(readline()))
    x::Vector{Int}=parseMap(split(readline()))
    t1::Int,t2::Int,t3::Int=parseMap(split(readline()))
    INF::Int=2<<32
    dp::Vector{Int}=[INF for i in 1:l+10]
    h::Vector{Bool}=[false for i in 1:l+10]
    for i in x
        h[i+1]=true
    end
    dp[1]=0
    for i in 1:l
        if h[i+1]
            dp[i+1]=min(dp[i+1],dp[i]+t1+t3)
        else
            dp[i+1]=min(dp[i+1],dp[i]+t1)
        end
        if h[i+2]
            dp[i+2]=min(dp[i+2],dp[i]+t1+t2+t3)
        else
            dp[i+2]=min(dp[i+2],dp[i]+t1+t2)
        end
        if h[i+4]
            dp[i+4]=min(dp[i+4],dp[i]+t1+t2*3+t3)
        else
            dp[i+4]=min(dp[i+4],dp[i]+t1+t2*3)
        end
        if i+1==l+1
            dp[l+1]=min(dp[l+1],dp[i]+t1÷2+t2÷2)
        elseif i+2==l+1
            dp[l+1]=min(dp[l+1],dp[i]+t1÷2+3*t2÷2)
        elseif i+3==l+1
            dp[l+1]=min(dp[l+1],dp[i]+t1÷2+5*t2÷2)
        end
    end
    println(dp[l+1])
end
main()

I - 行列操作

最初 N x Nの行列を生成してシミュレーションしようかと思ったんですが、10^5 x 10^5の行列を生成するとOutOfMemory()エラーが発生するのでおとなしく書き直しました。~~Juliaだと転置が(行列)' だけで済むから楽なのに・・・！~~

転置しているかどうかを示すフラグを用意しておき、trueの時は行を列、列を行と読み換えればよいです。分かりやすいプログラミングを心掛けているのでフラグ名は"tenchi"です。
Submission #14270362 - 第三回アルゴリズム実技検定

function main()
    n::Int=parseInt(readline())
    q::Int=parseInt(readline())
    gyo::Vector{Int}=[i for i in 1:n]
    retsu::Vector{Int}=[i for i in 1:n]
    tenchi::Bool=false
    for i in 1:q
        s::Vector{Int}=parseMap(split(readline()))
        if (s[1]==1 && !tenchi) || (s[1]==2 && tenchi)
            gyo[s[2]],gyo[s[3]]=gyo[s[3]],gyo[s[2]]
        elseif (s[1]==1 && tenchi) || (s[1]==2 && !tenchi)
            retsu[s[2]],retsu[s[3]]=retsu[s[3]],retsu[s[2]]
        elseif s[1]==3
            tenchi=!tenchi
        else
            if tenchi
                println(n*(gyo[s[3]]-1)+retsu[s[2]]-1)
            else
                println(n*(gyo[s[2]]-1)+retsu[s[3]]-1)
            end
        end
    end
end
main()

解けなかった問題

J - 回転寿司

各子供達が食べた寿司は常に降順ソートされた状態になっているとヒントをもらったので後は二分探索するだけでした。400点くらいありそうな気がします。
searchsortedfirst(arr,x,rev=true)はarr[i-1]≧x≧arr[i] となる最小のインデックスを返す関数です。今回は過去に食べた寿司よりおいしい寿司を食べる必要があり、同じおいしさのインデックスを返さないように-1しています。
Submission #14214279 - 第三回アルゴリズム実技検定

function main()
    n::Int,m::Int=parseMap(split(readline()))
    a::Vector{Int}=parseMap(split(readline()))
    eat::Vector{Int}=zeros(Int,n)
    for i in a
        index::Int=searchsortedfirst(eat,i-1,rev=true)
        if index<n+1
            eat[index]=i
            println(index)
        else
            println(-1)
        end
    end
end
main()

K - コンテナの移動

解説AC。UnionFindで解くのかと思っていたのですが、各コンテナの一つ下と各机の頂上をそれぞれ持っておけばいいらしくもんげー(死語)ってなりました。答えは各机の頂上から順に辿って見つかったらその机の番号を答えを入れる配列に格納していけばいいです。
Submission #14271973 - 第三回アルゴリズム実技検定

function main()
    n::Int,q::Int=parseMap(split(readline()))
    shita::Vector{Int}=[0 for i in 1:n]
    chojo::Vector{Int}=[i for i in 1:n]
    for i in 1:q
        f::Int,t::Int,x::Int=parseMap(split(readline()))
        shita[x],chojo[f],chojo[t]=chojo[t],shita[x],chojo[f]
    end
    
    ans::Vector{Int}=[0 for i in 1:n]
    for i in 1:n
        now::Int=chojo[i]
        while now>0
            ans[now]=i
            now=shita[now]
        end
    end
    println(join(ans,"\n"))
end
main()

L - スーパーマーケット

f:id:halss:20200614201043p:plain
11TLE+6REしました。ダメだったポイントは

Vectorで無理やり押し通そうとした(毎回findmaxしていた、間に合わない)
JuliaのPriorityQueueの使いにくさ
データの入れ替える場面でつまづいた

だと思います。
PriorityQueueはkey=>valueの形式で保存されるので列=>賞味期限として各列の1個目をFIRST、2個目をSECONDに挿入していきました。また各列において次に挿入する要素の場所を指すnextという配列をもち、a[i]==1もしくはFIRSTの最大値の方が大きいとき(PriorityQueueは昇順なので－1をかけています)にはFIRSTから取り出すdequeue!を行います。それ以外の場合はSECONDから最大値を取り出し、新しく詰めなおす作業を行うことを繰り返すと解けます。
本番中ではまるで南極の氷のように全く解けず、座っている椅子だけが温まっていきました。競プロを始めてから椅子温めばかりがうまくなっていく気がします。
Submission #14279025 - 第三回アルゴリズム実技検定

using DataStructures
 
function main()
    n::Int=parseInt(readline())
    data::Vector{Vector{Int}}=[parseMap(split(readline())) for _ in 1:n]
    m::Int=parseInt(readline())
    a::Vector{Int}=parseMap(split(readline()))
 
    FIRST=PriorityQueue{Int,Int}()
    SECOND=PriorityQueue{Int,Int}()
    next::Vector{Int}=fill(3,n)
    for i in 1:n
        enqueue!(FIRST,i,-data[i][2])
        if data[i][1]>1
            enqueue!(SECOND,i,-data[i][3])
        else
            enqueue!(SECOND,i,0)
        end
    end
 
    for i in a
        f_max::Pair{Int,Int}=peek(FIRST)
        s_max::Pair{Int,Int}=peek(SECOND)
        if i==1
            println(-f_max[2])
            dequeue!(FIRST)
            enqueue!(FIRST,dequeue_pair!(SECOND,f_max[1]))
            if next[f_max[1]]<=data[f_max[1]][1]
                enqueue!(SECOND,f_max[1],-data[f_max[1]][next[f_max[1]]+1])
                next[f_max[1]]+=1
            else
                enqueue!(SECOND,f_max[1],0)
            end
        else
            if s_max[2]<f_max[2]
                println(-s_max[2])
                dequeue!(SECOND)
                if next[s_max[1]]<=data[s_max[1]][1]
                    enqueue!(SECOND,s_max[1],-data[s_max[1]][next[s_max[1]]+1])
                    next[s_max[1]]+=1
                else
                    enqueue!(SECOND,s_max[1],0)
                end
            else
                println(-f_max[2])
                dequeue!(FIRST)
                enqueue!(FIRST,dequeue_pair!(SECOND,f_max[1]))
                if next[f_max[1]]<=data[f_max[1]][1]
                    enqueue!(SECOND,f_max[1],-data[f_max[1]][next[f_max[1]]+1])
                    next[f_max[1]]+=1
                else
                    enqueue!(SECOND,f_max[1],0)
                end
            end
        end
    end
end
main()

あとがき

ここまで全部解いてようやく80点・上級なので、上級以上の方々には頭が上がりません。しかし「実るほど頭が下がる稲穂かな」という言葉もあるので僕の方が実っている可能性だってあります。嘘です。人格者こそ頭の低い謙虚な姿勢であるという意味の言葉です。
次回までにもう少し言語仕様に慣れつつレートを上げて、水色上級を目指したいと思います。

~~あと、v0.5だとDataStructures.jlがないのではやく過去問もv1.4対応してください～～～～！！！！！AtCoderサマ！！靴までなら舐めます！！！！~~
過去問にもv1.4が適用されたみたいです！ありがとうございます！