気になっている問題

昨日,解法と共に知った問題.メモ.

n個の要素が与えられる.

また,2つの要素を受け取り,同じか否かを判定する判定機が与えられる.

この判定機を用いて n/2よりも多く同じものがあるかを判定したい.

計算時間は判定機の使用回数とする.

例)

{A, A, B, C} = False.

{A, A, A, B} = Ture.

{A, A, A, B, C} = Ture.

判定機は同値性判定を行なうのであって,比較はできない(主に[1]に関係してくる).

(1) O(n log n)の判定アルゴリズムを構成せよ.

(2) O(n)の判定アルゴリズムを構成せよ.

(3) 「n/3より多く同じものがあるか判定せよ」 という問題を考えた場合,O(n)のアルゴリズムは存在するか.

(1), (2)の答えは知っている.

(1)は易しめ,(2)は結構難しい.

自分は,直観的には線形でできると思わなかった.はじめて考えた人はエライ.

問題は(2)を拡張して,(3)ができるか.

できそうなんだけどなあ.

追記 2010年 11月 30日 火曜日 21:19:13

id:yambiと議論した結果,解けた.