Datalore

プログラム例と解説

2016年国内予選問題A 被験者の選定

\(a_1,a_2,\ldots,a_n\)から\(\min\{\lvert a_i-a_j\rvert \mid i\not=j\}\)を求める問題です。

素朴なアルゴリズムとしては、\(1\le i\lt j\le n\)をみたすすべての組み合わせ\((i,j)\)について\(\lvert a_i-a_j\rvert\)を計算して、それらの最小値を求めるものがあります。 時間計算量は\(O(n^2)\)となりますが、この問題の規模では支障ありません。このアルゴリズムは二重ループで簡単に実装できます

\(a_1,a_2,\ldots,a_n\)を先にソートして、その後で隣接する数の差の最小値を求めるアルゴリズムは、時間計算量\(O(n\log n)\)です。ただし、時間計算量\(O(n\log n)\)のソートアルゴリズムを採用するものとします。 C++では、std::vectorstd::sortを使って簡単に実装できます

ソートされた状態を保ったままの効率の良い挿入が可能なデータ構造を用いても、時間計算量\(O(n\log n)\)が可能です。ただし、挿入が時間計算量\(O(\log n)\)で実現できるデータ構造を採用するものとします。C++では、std::multisetを使って簡単に実装できます


戻る