[問題案] 並べ替えゲーム

[sotanishy]

問題: 謎の数字 $x_1,x_2,\dots,x_N$ がある． $(x_1,x_2,\dots,x_N)$ は $(1,2,\dots,N)$ の順列である．1回の質問では， $x_i$ と $x_j$ を選んでそれらの大小を聞くことができる．できるだけ少ない質問回数で $x_1,x_2,\dots,x_N$ を昇順に並べよ

• 簡単: $N^2/2$ 回以内
• 難しい: $N \log N$ 回以内

解法: ソートアルゴリズムなら何でも良い

• 簡単: バブルソート，挿入ソートなどの $O(N^2)$ アルゴリズム
• 難しい: マージソートなどの $O(N\log N)$ アルゴリズム

質問回数について: 質問回数を指定するよりは，「できるだけ少ない質問回数でやってみてください．これくらいの質問回数でできればこれくらいの難しさです」みたいな感じにしたほうが教育目的としては良い気がする．

$N$ の設定について: 手動でやることを考えると $N=8$ とかが丁度いいのかなあ． $O(N^2)$ が可能ではあるがめんどくさいと思われることが重要だと思っている

[kitsuya0828]

とりあえずこっちやってみます。

$N$ の設定について: 手動でやることを考えると $N=8$ とかが丁度いいのかなあ． $O(N^2)$ が可能ではあるがめんどくさいと思われることが重要だと思っている

これについては納得です。とりあえず $N=8$ で書いてみます！

[sotanishy]

「順列」「昇順」とかの言葉はいきなり初心者に見せるのは厳しいから，「並べ替えたもの」とか「小さい方から大きい方」みたいな感じの表現にしたほうがいいかなあ

[kitsuya0828]

なるほど確かに。一応UIは大小迷わないようにこうしておいたよ。 並べながら質問して推理していくイメージ。

https://user-images.githubusercontent.com/60843722/224875712-fa52cdc6-7cd3-4083-8be2-f3fe9fc03418.mov

まだ暫定だけど。

[sotanishy]

これめっちゃいいね．

細かい注文をつけるとすれば

• ドロップダウンメニューと質問履歴のところも x_i を MathJax で表示できないかな？
• 質問番号は 1 から始めたほうが良さそう
• 「提出する」ボタンの説明を入れたほうが良さそう

[kitsuya0828]

MathJaxに関しては入れたかったけど、ドロップダウンとテーブルに適用できる方法が見つからなかった...（あったら教えてください🙏）

• [x] 質問番号を1から始める
• [x] 提出ボタンに説明を入れる

については修正しておきます👍

[sotanishy]

あとから動的に追加するテキストに MathJax を適用するには，MathJax.typeset() を明示的に呼び出す必要があるみたい．

参考: https://docs.mathjax.org/en/latest/advanced/typeset.html

テーブルについてはこれで解決できそう．ドロップダウンは，わからん......．

[kitsuya0828]

select要素にはスタイルを適用しないのが定石らしいです。 selectのoptionに効くCSSと効かないCSS

このままで一回プルリク出します。 部員の皆さんが触れる状態にして、改善点は都度修正でお願いしたいです。