Language Test 202001 - L Interactive Sorting に関するメモ書き

問題

$N$個のボールがあります。ボールの重さは相異なります。
あなたは$2$つのボールを選んで質問することで、そのどちらが重いかを知ることができます。ただし、質問回数が$Q$を上回ってはなりません。
ボールを軽い順にソートしてください。
$(N,Q)=(26,100)$の場合と$(N,Q)=(5,7)$の場合があります。

Q=26なら挿入ソート

長さ$N-1$の増加列には挿入可能な場所が（両端もあわせて）$N$個あるので、これに挿入するとき必要な質問回数は$\bigl \lceil \log_2N \bigr \rceil$です。
長さ$0$から始めると、合計の質問回数は$ \sum_{N=1}^{26} \bigl \lceil \log_2N \bigr \rceil = 99$回です。

Q=5なら……？

$Q = 26$と同様に挿入ソートをしようとすると$\sum_{N=1}^{5} \bigl \lceil \log_2N \bigr \rceil = 8$となり間に合いません。困った。

先人の知恵

Compare A to B and C to D. WLOG, suppose A>B and C>D. Compare A to C. WLOG, suppose A>C. Sort E into A-C-D. This can be done with two comparisons. Sort B into {E,C,D}. This can be done with two comparisons, for a total of seven.

つまりどういうことかというと、

3回目の質問を終えた時の図

5回目の質問を終えた時の図

らしいです。「い」→「ろ」が確定しているので、比較回数を1回減らせるようです。なるほど〜〜〜〜

余談

Pythonでやる場合は答えを出力したのちにexit()をするのがおすすめです。出力とまとめてexit(print("!",ans))でもよいです。他の言語は分かりません。

余談2

WIP

余談3（追記）

画像が入っているとAIフレンドリーではないかなと思って、Tikzで再現を試みた。「質問3の後」が上、「質問5の後」が左右、「余談2」が下に配置してある。OpenAI謹製の論文執筆プラットフォームであるPrismの力を借りたが、挿入順序を表す緑棒と矢印の再現はできなかった……

diagram.tex

% !TEX program = xelatex
% NOTE: Unicode 文字のため、XeLaTeX（または LuaLaTeX）でコンパイルしてください。
\documentclass[11pt]{article}
\usepackage{fontspec}
\usepackage{xeCJK}
\setmainfont{CMU Serif}
\IfFontExistsTF{Noto Serif CJK JP}{\setCJKmainfont{Noto Serif CJK JP}}{%
  \IfFontExistsTF{Source Han Serif JP}{\setCJKmainfont{Source Han Serif JP}}{%
    \IfFontExistsTF{HaranoAjiMincho}{\setCJKmainfont{HaranoAjiMincho}}{%
      \setCJKmainfont{IPAMincho}% last-resort fallback
    }%
  }%
}%
\usepackage[margin=1in]{geometry}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{tikz-cd}
\usetikzlibrary{positioning,arrows.meta,calc}

\setlength{\parindent}{0pt}
\setlength{\parskip}{1\baselineskip}

\begin{document}

\begin{center}
\begin{tikzpicture}[
  node distance=1.8cm,
  every node/.style={font=\large},
  circ/.style={draw,circle,minimum size=10mm,inner sep=0pt},
  small/.style={draw,circle,fill=gray!40,minimum size=4.2mm,inner sep=0pt},
  arr/.style={-Stealth}
]
  % nodes
  \node[small] (up_insert1) {};
  \node[circ, right=1.2cm of up_insert1] (up_i) {い};
  \node[circ, above right=1.2cm and 1.6cm of up_i] (up_ro) {ろ};
  \node[small, below right=0.6cm and 0.8cm of up_i] (up_insert2) {};
  \node[circ, below right=0.6cm and 0.8cm of up_insert2] (up_ha) {は};
  \node[small, right=1.2cm of up_ha] (up_insert3) {};
  \node[circ, right=1.2cm of up_insert3] (up_ni) {に};
  \node[small, right=1.2cm of up_ni] (up_insert4) {};
  \node[circ, right=4.0cm of up_ro] (up_ho) {ほ};

  % arrows
  \draw[arr, dashed] (up_insert1) -- (up_i);
  \draw[arr] (up_i) -- (up_ro);
  \draw (up_i) -- (up_insert2);
  \draw[arr] (up_insert2) -- (up_ha);
  \draw (up_ha) -- (up_insert3);
  \draw[arr] (up_insert3) -- (up_ni);
  \draw[arr, dashed] (up_ni) -- (up_insert4);
\end{tikzpicture}

\medskip
{\small（小丸は「ほ」の挿入可能位置）}
\end{center}

\begin{center}
\resizebox{\linewidth}{!}{%
\begin{tikzpicture}[
  node distance=1.8cm,
  every node/.style={font=\large},
  circ/.style={draw,circle,minimum size=8mm,inner sep=0pt},
  small/.style={draw,circle,fill=gray!40,minimum size=3.4mm,inner sep=0pt},
  arr/.style={-Stealth}
]
  % left diagram
  \node[circ] (left_ho) {ほ};
  \node[circ, right=1.0cm of left_ho] (left_i) {い};
  \node[circ, above right=0.8cm and 0.8cm of left_i] (left_ro) {ろ};
  \node[small, below right=0.4cm and 0.4cm of left_i] (left_insert1) {};
  \node[circ, below right=0.4cm and 0.4cm of left_insert1] (left_ha) {は};
  \node[small, right=0.5cm of left_ha] (left_insert2) {};
  \node[circ, right=0.5cm of left_insert2] (left_ni) {に};
  \node[small, right=0.5cm of left_ni] (left_insert3) {};

  \draw[arr] (left_ho) -- (left_i);
  \draw[arr] (left_i) -- (left_ro);
  \draw (left_i) -- (left_insert1);
  \draw[arr] (left_insert1) -- (left_ha);
  \draw (left_ha) -- (left_insert2);
  \draw[arr] (left_insert2) -- (left_ni);
  \draw[arr, dashed] (left_ni) -- (left_insert3);

  % separator text
  \node[font=\large, right=5.5cm of left_i] (label_alt) {または};

  % right diagram
  \node[circ, right=1.0cm of label_alt] (right_i) {い};
  \node[circ, above right=0.8cm and 0.8cm of right_i] (right_ro) {ろ};
  \node[small, below right=0.4cm and 0.4cm of right_i] (right_insert1) {};
  \node[circ, below right=0.4cm and 0.4cm of right_insert1] (right_q1) {？};
  \node[small, right=0.5cm of right_q1] (right_insert2) {};
  \node[circ, right=0.5cm of right_insert2] (right_q2) {？};
  \node[small, right=0.5cm of right_q2] (right_insert3) {};
  \node[circ, right=0.5cm of right_insert3] (right_q3) {？};
  \node[small, right=0.5cm of right_q3] (right_insert4) {};

  \draw[arr] (right_i) -- (right_ro);
  \draw (right_i) -- (right_insert1);
  \draw[arr] (right_insert1) -- (right_q1);
  \draw (right_q1) -- (right_insert2);
  \draw[arr] (right_insert2) -- (right_q2);
  \draw (right_q2) -- (right_insert3);
  \draw[arr] (right_insert3) -- (right_q3);
  \draw[arr, dashed] (right_q3) -- (right_insert4);
\end{tikzpicture}%
}

\medskip
{\small（小丸は「ろ」の挿入可能位置）}
\end{center}

\begin{center}
\resizebox{\linewidth}{!}{%
\begin{tikzpicture}[
  every node/.style={font=\large},
  circ/.style={draw,circle,minimum size=8mm,inner sep=0pt},
  arr/.style={-Stealth},
  vbar/.style={draw=green!50!black,line width=3pt}
]
  % top row (sorted)
  \node[circ] (t1) {と};
  \node[circ, right=0.9cm of t1] (t2) {へ};
  \node[circ, right=0.9cm of t2] (t3) {ほ};
  \node[circ, right=0.9cm of t3] (t4) {に};
  \node[circ, right=0.9cm of t4] (t5) {は};
  \node[circ, right=0.9cm of t5] (t6) {ろ};
  \node[circ, right=0.9cm of t6] (t7) {い};

  \draw[arr] (t2) -- (t1);
  \draw[arr] (t3) -- (t2);
  \draw[arr] (t4) -- (t3);
  \draw[arr] (t5) -- (t4);
  \draw[arr] (t6) -- (t5);
  \draw[arr] (t7) -- (t6);

  \node[font=\normalsize, above left=0.4cm and -0.2cm of t1] {ソート済};

  \draw[dashed] ($(t1)+(-0.7,0.6)$) rectangle ($(t7)+(0.7,-0.6)$);

  % second row
  \node[circ, below=0.9cm of t1] (b1) {か};
  \node[circ, below=0.9cm of t2] (b2) {わ};
  \node[circ, below=0.9cm of t3] (b3) {を};
  \node[circ, below=0.9cm of t4] (b4) {る};
  \node[circ, below=0.9cm of t5] (b5) {ぬ};
  \node[circ, below=0.9cm of t6] (b6) {り};
  \node[circ, below=0.9cm of t7] (b7) {ち};
  \node[circ, right=1.2cm of b7] (b8) {甲};

  \draw[arr] (t1) -- (b1);
  \draw[arr] (t2) -- (b2);
  \draw[arr] (t3) -- (b3);
  \draw[arr] (t4) -- (b4);
  \draw[arr] (t5) -- (b5);
  \draw[arr] (t6) -- (b6);
  \draw[arr] (t7) -- (b7);

  % vertical bars and indices
  \foreach \x/\lab in {0/1,1.7/2,3.9/3,6.2/4,8.6/5,10.9/6,13.2/7,15.6/8} {
    \draw[vbar] ($(t1)+(\x,-3.2)$) -- ($(t1)+(\x,-5.3)$);
    \node[font=\normalsize, below=2.5cm of t1, xshift=\x cm] {\lab};
  }

  % diagonal arrows
  \draw[fill=blue!20,draw=black] ($(t1)+(-0.1,-3.9)$) -- ($(t1)+(2.3,-3.4)$) -- ($(t1)+(2.4,-3.6)$) -- ($(t1)+(0.0,-4.1)$) -- cycle;
  \draw[fill=blue!20,draw=black] ($(t1)+(1.1,-4.4)$) -- ($(t1)+(4.6,-3.8)$) -- ($(t1)+(4.7,-4.0)$) -- ($(t1)+(1.2,-4.6)$) -- cycle;
  \draw[fill=blue!20,draw=black] ($(t1)+(3.8,-4.9)$) -- ($(t1)+(8.0,-4.3)$) -- ($(t1)+(8.1,-4.5)$) -- ($(t1)+(3.9,-5.1)$) -- cycle;
  \draw[fill=blue!20,draw=black] ($(t1)+(7.2,-5.4)$) -- ($(t1)+(14.6,-4.7)$) -- ($(t1)+(14.7,-4.9)$) -- ($(t1)+(7.3,-5.6)$) -- cycle;

  % bounds labels
  \node[font=\normalsize, below=5.8cm of t1, xshift=0.8cm] {$\leq J_1$};
  \node[font=\normalsize, below=5.8cm of t1, xshift=2.6cm] {$\leq J_2$};
  \node[font=\normalsize, below=5.8cm of t1, xshift=5.0cm] {$\leq J_3$};
  \node[font=\normalsize, below=5.8cm of t1, xshift=9.2cm] {$\leq J_4\,(=11)$};
  \node[font=\normalsize, below=5.1cm of t1, xshift=14.8cm] {※};
\end{tikzpicture}%
}

\[
  J_n =
  \begin{cases}
    2n - 1 & (n \in [1,3]) \\
    2J_{n-2} + J_{n-1} & (\text{otherwise})
  \end{cases}
\]

\medskip
{\small ※挿入順序を書き下すと 1,3,2,5,4,8,7,6 となる}
\end{center}

\end{document}