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

# 前回まで

https://qiita.com/dannchu/items/053b69d23b8887c0130e

https://qiita.com/dannchu/items/4cdce0c86f081ce1123a

https://qiita.com/dannchu/items/ca561fa8d1a59b7f5899



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

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

# practice contest

## B - Interactive Sorting

<img width="1177" alt="スクリーンショット 2019-07-26 12.52.39.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426542/d21e0610-a545-5a00-2905-be4c847c26a1.png">

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

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

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

いよいよ(3)です。まず，どうして『$N=5$，$Q=7$なのか？』です。


前回の(2)をマージソートで処理をしました。マージソートのオーダーは$O(n\log n)$で，挿入ソートの$O(n^2)$よりも回数が少ないものでした。

$n=5$の時の$n\log n$を計算してみると，

$$5\log 5=8.047189...>8>7$$

** マージソートよりももっと効率を高めなければならない！？ **

まず，少し調べることにしました。

## 5個を7回でソートする


まずは，下記のサイト（pdf）を見ました。

http://www.f.waseda.jp/moriya/PUBLIC_HTML/social/sorting_continued.pdf

そこに書いてあったのは

<img width="474" alt="スクリーンショット 2019-07-26 14.22.53.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426542/4b2bef27-dd0c-cdaf-674b-7b3f7bc11110.png">

ということでした。（実際の構成はありませんでした。）

次に，次のサイトを見ました。

http://quiz-tairiku.com/q.cgi?mode=view&no=12306

10年くらい前のクイズのサイトですが，ここで，実装した方がいました。

このサイトによると，$n\log n$の値から減らせても1だけあるとも書いてありました。

<img width="535" alt="スクリーンショット 2019-07-26 14.30.12.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426542/17305cca-8328-2925-14c9-45928be6a9d0.png">

<img width="629" alt="スクリーンショット 2019-07-26 14.31.13.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426542/13d74e5a-50de-f890-7b7e-445ec4e3b29c.png">

最初のものは途中で，大変だったので，後半の方の意見を参考に場合分けを作ることにしました。

前半は(2)のマージソートで，$n=5$の時を別立てにしました。

```Julia:B-InteractiveSorting3
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 n5t7(x)

# 1回目
println("? ",x[1]," ",x[2]) 
if readline()==">\n"
    x[1],x[2],x[3],x[4],x[5]=x[2],x[1],x[3],x[4],x[5]
else
    x[1],x[2],x[3],x[4],x[5]=x[1],x[2],x[3],x[4],x[5]
end

#2回目
println("? ",x[3]," ",x[4]) 
if readline()==">\n"
    x[1],x[2],x[3],x[4],x[5]=x[1],x[2],x[4],x[3],x[5]
else
    x[1],x[2],x[3],x[4],x[5]=x[1],x[2],x[3],x[4],x[5]
end

#3回目
println("? ",x[1]," ",x[3]) 
if readline()==">\n"
    x[1],x[2],x[3],x[4],x[5]=x[3],x[1],x[2],x[4],x[5]
else
    x[1],x[2],x[3],x[4],x[5]=x[1],x[3],x[4],x[2],x[5]
    #acdbe
    #01eabcd,02aebcd,03abecd,04abced,05abcde,
    #06eacbd,07aecbd,08acebd,09acbed,10acbde,
    #11eacdb,12aecdb,13acedb,14acdeb,15acdbe,
end
end

function nnnt(x)
#4回目
println("? ",x[2]," ",x[5]) #ce
if readline()==">\n"
    #acdbe,e<c
    #01eabcd,02aebcd,03abecd,06eacbd,07aecbd,11eacdb,12aecdb,
    #5回目
    println("? ",x[1]," ",x[5])
    if readline()==">\n"
        #acdbe,e<a<c
        #01eabcd,06eacbd,11eacdb,
        #6回目
        println("? ",x[2]," ",x[4])
        if readline()==">\n"
            #acdbe,e<a<b<c
            #01eabcd
            x[1],x[2],x[3],x[4],x[5]=x[5],x[1],x[4],x[2],x[3]#確定01
        else
            #acdbe,e<a<c<b
            #06eacbd,11eacdb,
            #7回目
            println("? ",x[3]," ",x[4])
            if readline()==">\n"
                #acdbe,e<a<c<b<d
                #06eacbd,
                x[1],x[2],x[3],x[4],x[5]=x[5],x[1],x[2],x[4],x[3]#確定06
            else
                #acdbe,e<a<c<b<d
                #11eacdb,
                x[1],x[2],x[3],x[4],x[5]=x[5],x[1],x[2],x[3],x[4]#確定11
            end
        end
    else
        #acdbe,a<e<c
        #02aebcd,03abecd,07aecbd,12aecdb,
        #6回目
        println("? ",x[2]," ",x[4])
        if readline()==">\n"
            #acdbe,a<b<e<c or a<e<b<c
            #02aebcd,03abecd,
            #7回目
            println("? ",x[5]," ",x[4])
            if readline()==">\n"
                #acdbe,a<b<e<c
                #03abecd,
                x[1],x[2],x[3],x[4],x[5]=x[1],x[4],x[5],x[2],x[3]#確定03
            else
                #acdbe,a<e<b<c
                #02aebcd,
                x[1],x[2],x[3],x[4],x[5]=x[1],x[5],x[4],x[2],x[3]#確定02
            end
        else
            #acdbe,a<e<c<b
            #07aecbd,12aecdb,
            #7回目
            println("? ",x[3]," ",x[4])
            if readline()==">\n"
                #acdbe,a<e<c<d<b
                #07aecbd
                x[1],x[2],x[3],x[4],x[5]=x[1],x[5],x[2],x[4],x[3]#確定07
            else
                #acdbe,a<e<c<b<d
                #12aecdb,
                x[1],x[2],x[3],x[4],x[5]=x[1],x[5],x[2],x[3],x[4]#確定12
            end
        end
    end
else
    #acdbe,c<e
    #04abced,05abcde,08acebd,09acbed,10acbde,13acedb,14acdeb,15acdbe,
    #5回目
    println("? ",x[3]," ",x[5])#de
    if readline()==">\n"
        #acdbe,c<e<d
        #04abced,08acebd,09acbed,13acedb,
        #6回目
        println("? ",x[4]," ",x[5])
        if readline()==">\n"
            #acdbe,c<e<d,e<b
            #08acebd,13acedb,
            #7回目
            println("? ",x[3]," ",x[4])
            if readline()==">\n"
                #acdbe,c<e<b<d
                #08acebd,
                x[1],x[2],x[3],x[4],x[5]=x[1],x[2],x[5],x[4],x[3]#確定08
            else
                #acdbe,c<e<d<b
                #13acedb,
                x[1],x[2],x[3],x[4],x[5]=x[1],x[2],x[5],x[3],x[4]#確定13
            end
        else
            #acdbe,c<e<d,b<e
            #04abced,09acbed
            #7回目
            println("? ",x[2]," ",x[4])
            if readline()==">\n"
                #acdbe,c<e<d,b<e,b<c
                #04abced
                x[1],x[2],x[3],x[4],x[5]=x[1],x[4],x[2],x[5],x[3]#確定04
            else
                #acdbe,c<e<d,b<e,c<b
                #09acbed
                x[1],x[2],x[3],x[4],x[5]=x[1],x[2],x[4],x[5],x[3]#確定09
            end
        end
    else
        #acdbe,c<d<e
        #05abcde,10acbde,14acdeb,15acdbe,
        #6回目
        println("? ",x[3]," ",x[4])
        if readline()==">\n"
            #acdbe,c<d<e,b<d
            #05abcde,10acbde,
            #7回目
            println("? ",x[2]," ",x[4])
            if readline()==">\n"
                #acdbe,c<d<e,b<d,b<c
                #05abcde
                x[1],x[2],x[3],x[4],x[5]=x[1],x[4],x[2],x[3],x[5]#確定05
            else
                #acdbe,c<d<e,b<d,c<b
                #10acbde,
                x[1],x[2],x[3],x[4],x[5]=x[1],x[2],x[4],x[3],x[5]#確定10
            end
        else
            #acdbe,c<d<e,d<b
            #14acdeb,15acdbe,
            #7回目
            println("? ",x[5]," ",x[4])
            if readline()==">\n"
                #acdbe,c<d<e,d<b,b<e
                #15acdbe,
                x[1],x[2],x[3],x[4],x[5]=x[1],x[2],x[3],x[4],x[5]#確定15
            else
                #acdbe,c<d<e,d<b,e<b
                #14acdeb,
                x[1],x[2],x[3],x[4],x[5]=x[1],x[2],x[3],x[5],x[4]#確定14
            end
        end
    end
end
end


function main()

if n==5
    n5t7(X)
    nnnt(X)
  else
    mergeSort(X)
  end

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

end
main()
```

＜感想＞

- (3) $N=5$，$Q=7$をチェックするファイルは50個あります。(2)のマージソートで臨むと，50個中25個は通ります。半分の25個は通りません。すなわち，25個はマージソートでも7回以内で終わります。しかし，残りの25個は8回というわけです。

- 最初『できた！』と思って回したら，50個中34個が通りました。16個がエラーです。これは悩みました。全部できないのであれば，わかりやすいのですが，部分的にできない。。。。なぜだろう。。。

- 違ったアウトプットの例から間違いを探しました。１カ所不等号の向きが違っていて，見つけた時はちょっと嬉しかったのですが，『もうちょっとうまくコードを書かないといけないな。。。』とも思いました。

- やっていることはマージソートと同じような感じなので，『１回減らすのは本当にちょっとした差なのだな。』と思いました。

（終わりです）