JuliaでAtCoderのpractice contestをやってみた（３）

前回まで

Julia言語の練習をしています。AtCoderのbeginnerあたりならば手頃なのかなと思って，やってみました。

practice contestのB - Interactive Sortingの続きです。

practice contest

B - Interactive Sorting

問題はインタラクティブ（どちらが大きいか質問しながら）に文字をソートします。

要素の個数$N$と質問回数$Q$に制限があります。

(1) $N=26$，$Q=1000$
(2) $N=26$，$Q=100$
(3) $N=5$，$Q=7$

(1)は前回解決したので，(2)です。前回のソートの考え方では終わらないので，別なソート方法で考えなくてはなりません。

自分で考えても良かったのですが，ソート方法を色々調べてみることにしました。

＜参考サイト＞

このサイトを見て，ソートについてよくわかりました。
前回(1)で行ったソートは挿入ソートと呼ばれていて，$O(n^2)$のオーダーということもわかりました。

そして，このオーダーを$O(n\log n)$とできるマージソートが紹介されていたので，これでやってみようと思いました。

マージソート

今回，$O(n\log n)$のオーダーでソートできるとすると，$n=26$なので，
$$26\log 26=84.7105...<100$$
なので，(2)$N=26$，$Q=100$をクリアできそうです。

＜参考サイト＞

Juilaで書いたマージソートがあったので，利用させてもらいました。

B-InteractiveSorting2

nq=readline()
nq1=split(nq)
n=parse(Int,nq1[1])
q=parse(Int,nq1[2])
X=Any[]
for i=0:n-1
    X= push!(X , "$('A'+i)")
end

#
# Merge Sort
#

function mergeSort(A)

  Anew = copy(A)
  mergesort_array(Anew,  A,  1,  length(A)+1)

end

function mergesort_array(A, result, left, right)

  if right - left < 2 # Aが１個しかなかったら，そのまま返せ。
    return
  end
  if right - left == 2　# Aが２個だったら，大小を比較して返せ。
        println("? ",result[left]," ",result[left+1])
    if readline()==">\n"
      result[left],  result[left+1] = result[left+1], result[left]
    end
    return
  end

  mid = Int(round((right + left) / 2))
  mergesort_array(result, A, left,  mid)
  mergesort_array(result, A, mid, right)

  i = left
  j = mid
  idx = left
  while idx < right
    if j >= right|| (i < mid && (println("? ",A[i]," ",A[j]) ;readline()=="<\n"))
      result[idx] = A[i]
      i = i + 1
    else
      result[idx] = A[j]
      j = j + 1
    end
    idx = idx + 1
  end

end

function main()
mergeSort(X)

z="! "
for i=1:n
    z*=X[i]
end
println(z)
end
main()

悩んだところは

(println("? ",A[i]," ",A[j]) ;readline()=="<\n")

です。毎回，同じようなところで悩みます。

(2) $N=26$，$Q=100$も無事クリア！残るは(3) $N=5$，$Q=7$のみです。（続く）