読者です 読者をやめる 読者になる 読者になる

「サマーインターン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)

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