前回まで
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$
いよいよ(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）を見ました。
そこに書いてあったのは
ということでした。（実際の構成はありませんでした。）
次に，次のサイトを見ました。
10年くらい前のクイズのサイトですが，ここで，実装した方がいました。
このサイトによると，$n\log n$の値から減らせても1だけあるとも書いてありました。
最初のものは途中で，大変だったので，後半の方の意見を参考に場合分けを作ることにしました。
前半は(2)のマージソートで，$n=5$の時を別立てにしました。
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個がエラーです。これは悩みました。全部できないのであれば，わかりやすいのですが，部分的にできない。。。。なぜだろう。。。
違ったアウトプットの例から間違いを探しました。１カ所不等号の向きが違っていて，見つけた時はちょっと嬉しかったのですが，『もうちょっとうまくコードを書かないといけないな。。。』とも思いました。
やっていることはマージソートと同じような感じなので，『１回減らすのは本当にちょっとした差なのだな。』と思いました。
（終わりです）