「サマーインターン2011問題 : Preferred Research」について考えてみる

今更ながら，「サマーインターン2011問題 : Preferred Research」について考えたので，ここにメモ．

問題の概要を箇条書きにすると

• 長さ n の文字列 s が与えられる
• s に含まれる文字の中で，出現回数が最も大きい文字を出力せよ
• ただし，出現回数が最大の文字の出現回数は n/2 より大きい
• 計算時間は O(n) でなければならない
• 空間使用量は s を格納するバッファを除いて O(1) でなければならない
• s を格納するバッファは書き換えてよい

解法1

よく考えると，s をソートしたときに n/2 番目に来る要素は，出現回数が最大の文字であることがわかります．「ソートしたときに k 番目に来る要素」というのは，実際にソートをしなくても O(n) で求めることができ，問題の条件を満たします．C++ の標準ライブラリには nth_element という関数が用意されており，これを使うと簡単に「ソートしたときに k 番目に来る要素」を計算できます．

解法2

次のアルゴリズムを考えます．

for (;;) {
  添字 i を [0, n) からランダムに選ぶ;
  文字 s[i] の出現回数をリニアにカウントする;
  if (s[i] の出現回数 > n/2) return s[i];
}

1回の反復で答えが求まる確率は少なくとも1/2あるので，平均計算時間は

(1 + 1/2 + 1/4 + ...) O(n) = O(n)

となり問題の条件を満たします．