AtCoder ABC 104 C - All Green を嘘解法で (Julia) （おまけ：ABC 116 D - Various Sushi をJuliaで書き直し）

irisruneです。今回もJuliaで問題を解いてみました。おまけで以前Go言語で解いた問題も解き直して実行時間など比較しています。

ABC 104 C - All Green

atcoder.jp

当時2完で冷えた回ですが、今見ても300点にしては難しいと思います。なお嘘解法でゴリ押しです。

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

function iter(d::Int, pc::Array{Int, 2}, g::Int)
    if g <= 0 return(0) end
    ret = typemax(Int)
    for i in d:-1:1
        if pc[i,1]==0 continue end
        if g <= pc[i,1] * 100i
            ret = min(ret, ceil(Int, g / 100i))
        else
            pcNext = copy(pc)
            pcNext[i, 1] = 0
            ret = min(ret, pc[i,1] + iter(d, pcNext, g - ((100i * pc[i,1]) + pc[i,2])))
        end
    end
    return(ret)
end

function main()
    d, g = readline() |> split |> parseMap

    pc = zeros(Int, d, 2)
    for i in 1:d
        pc[i, 1], pc[i, 2] = readline() |> split |> parseMap
    end

    ans = iter(d, pc, g)
    println(ans)

end

main()

アルゴリズムとしては、スコアの高い問題セットから順番に見ていき、各問題セットについて解くと仮定した時の解くべき問題数を再帰で計算してその最小値を取るというものになります。

このアルゴリズムの問題として解く問題セットの組み合わせに重複が発生するため計算量がかなり大きいです。例を挙げると、

• 最初に500点の問題セットを解き、再帰関数内で400点の問題セットを解く場合
• 最初に400点の問題セットを解き、再帰関数内で500点の問題セットを解く場合

このように全完する問題セットの順列の総数分の重複が発生してしまっています。そのため計算量はと想定解答より大きくなるはずです。

なお、再帰関数のパラメータとして既に見た問題セットを記録するようにしておけば想定解と同じ計算量になるとは思います…が残念ながら上手く実装できませんでした。

全体的な感想として、やはりビット全探索は使えるに越したことはなさそうですね。

コードレビュー

• 再帰：Recursion　反復：Iteration
  • よくやらかします。

ABC 116 D - Various Sushi

atcoder.jp

以前Go言語で解いた記事はこちら。

ami-atcoder.hatenablog.com

こちらで書いたGoのコードをほぼそのままJuliaに移植してみました。

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

pointSum(pointD, typeNum) = pointD + (typeNum * typeNum)

function main()
    n, k = readline() |> split |> parseMap
    sushi = zeros(Int, n, 2)
    for i in 1:n
        sushi[i,2], sushi[i,1] = readline() |> split |> parseMap
        # 種類が後の方が都合がよいので
    end
    sushi = sortrows(sushi, rev=true)

    pointD = 0
    typeNum = 0
    types = zeros(Int, n)
    for i in 1:k
        pointD += sushi[i, 1]
        types[sushi[i, 2]] += 1
        if types[sushi[i, 2]] == 1
            typeNum += 1
        end
    end

    ans = pointSum(pointD, typeNum)

    iRemove = k
    iAdd = k + 1

    while typeNum < k
        while iRemove > 1
            if types[sushi[iRemove, 2]] > 1
                pointD -= sushi[iRemove, 1]
                types[sushi[iRemove, 2]] -= 1
                break
            end
            iRemove -= 1
        end
        if iRemove == 1 break end
        iRemove -= 1

        while iAdd <= n
            if types[sushi[iAdd, 2]] == 0
                pointD += sushi[iAdd, 1]
                types[sushi[iAdd, 2]] += 1
                typeNum += 1
                break
            end
            iAdd += 1
        end
        if iAdd > n break end
        iAdd += 1

        ans = max(ans, pointSum(pointD, typeNum))
    end
    println(ans)
end

main()

画像のように、Goよりも少し速くなっています。もっともGoは入力部分を最適化していなくてJuliaは（多分）最適化しているという違いがありますが。

バイト数で見るとJuliaの方が少し多く、Goではソートに記述量を使っていることを考えるとGoの方が記述が簡潔と言えるかもしれません（Goの入力部分を最適化するのにも記述量は必要だと思いますが）。メモリ使用量は見なかったことにしましょう。

行列を行単位・列単位でソートできるという機能を活用したのでJuliaの良いところを少し出せたとは思いますが、やはり競プロ向きといった感じではなさそうな気もします。

なお、REを出しているのは手元のJulia1.1でsortrowsではなくsortslicesを使っていたためでした。一応スクリプト言語的な立ち位置なのでCEではないんですね…

雑記

• AtomのJuliaプラグインで書いてみましたが、エディタ部分の動作は良好だと思いました。ただREPLに複数行入力できないのが厳しいですね（Julia実行環境自体がそういう仕様ですが）。
  • IntelliJのJuliaプラグインの場合は複数行入力の方法があるのでその点では分がありますね。エディタ部分の動作に難しかないのでそこさえ何とかなれば…