前回まで
Julia言語の練習をしています。AtCoderのbeginnerあたりならば手頃なのかなと思って，やってみました。
practice contestのA - Welcome to AtCoderに続いて，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$
それぞれ100点，合計300点満点です。
『何が違うのかな？』と思いながら，スタートです。
挿入ソート
『挿入ソート』という呼び名は確認しました。手順は次の通りです。
- まず，は１番目（左端）と２番目（その右隣）を比較し，１番目の方が大きければ，１番目と２番目の要素を入れ替えます。
- 次に２番目と３番目を比較し，大きい方を右側来るようにします。
- 順次同様に繰り返し，$N-1$番目と$N$番目まで行います。すると，$N$番目に一番大きい数が来ることになります。
- 再び，１番目と2番目から同じ操作を再び行うと，$N-1$番目に２番目に大きな数がきます。
- このように繰り返していくと，ソートが完了します。
今回のソートでは
- 最初のターンは$N-1$回の質問です。
- ２番目のターンは$N-2$回の質問です。
- 一般に$k$番目のターンは$N-k$回の質問で$1\leqq k\leqq N-1$です。
質問の回数は
$$Q=\sum_{k=1}^{N-1}(N-k)=N(N-1)-\frac{N(N-1)}2=\frac{N(N-1)}2$$
となります。$N=26$のとき，$Q=26\times25/2=325$なので，(2)はだめだけど，(1)は行けそうです。
問題のサンプル解答（Juliaはやはりありません。。。）もこの方針のようで，この解答だと300点満点中100点だと書いてあります。
コード
さて，コードです。
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
for j=1:n-1
for i=1:n-j
println("? ",x[i]," ",x[i+1])
if readline()==">\n"
x[i],x[i+1]=x[i+1],x[i]
else
end
end
end
z="! "
for i=1:n
z*=x[i]
end
println(z)
考えたことは
- アルファベット２６文字の要素をどう用意するか？（上のコードのようにしました。）
- 要素を入れ替える時どうすればいいのか？ 何か
swapみたいな関数があるのかな？と思っていましたが，単純にx[i],x[i+1]=x[i+1],x[i]と書けば良いことがわかりました。
悩んだことはreadline()==">\n"のところです。Jupyter NotebookのJulia1.1.1ではreadline()==">"で良かったのですが，そのまま，AtCoderのJulia0.5.0では合格となりませんでした。悩むのはこんなところばっかりです。
でもなんとか(1) $N=26$，$Q=1000$はクリアで，
100点/300点は取れました。（続く）